Recursive Thinking

Recursion solves a problem by reducing it to smaller instances of the same problem until it reaches a case with a known answer. Whereas mathematical induction and forward iteration start from a base case, recursion works toward a base case to determine the solution for a non-base case.

An Analogy

Suppose the line at a restaurant stretches out the door, and someone near the back wants to know their place in line. Walking to the front to count would mean losing their spot, so instead they ask the person ahead of them what their place in line is. That person doesn’t know their place in line either, so they ask the person ahead of them what their place in line is, and so on, until the question reaches the person at the front of the line, who answers “1.” The person behind them now knows their position in line is 2, and they tell the person behind them, and so on until the answers reach the person at the end of the line.

This works because the problem contains a smaller copy of itself: the last person’s place in a line of 10 is one more than the place of the person ahead in a line of 9. If \(p(N)\) is the last person’s place in a line of \(N\) people, then

\[ p(N) = 1 + p(N-1), \qquad p(1) = 1. \]

This is a recursive formulation because it states the problem in terms of a smaller version of the same problem.

Recursive Functions

In code, a recursive function is a function that calls itself. It needs at least one of each of the following, usually separated by an if statement.

  • A base case, an input whose answer is known directly, without calling the function again.

  • A recursive case, where the function calls itself with an input closer to a base case and uses the result.

In the line analogy, the base case is “if there is no one in front of me, I am the first person in line” and the recursive case is “my place in line is 1 plus the place of the person in front of me.” The following pseudocode captures this idea.

def place_in_line(person):
    if no_one_in_front_of(person):  # Base case: the first person in line.
        return 1
    return 1 + place_in_line(person_ahead_of(person))  # Recursive case.

Suppose Zane is at the back of the line, behind Yvonne, Xander, Whitney, and Vance, who is at the front. The base case gives place_in_line(Vance) = 1, so the call place_in_line(Zane) unfolds as follows.

place_in_line(Zane) = 1 + place_in_line(Yvonne)
                    = 1 + (1 + place_in_line(Xander))
                    = 1 + (1 + (1 + place_in_line(Whitney)))
                    = 1 + (1 + (1 + (1 + place_in_line(Vance))))
                    = 1 + (1 + (1 + (1 + 1)))
                    = 1 + (1 + (1 + 2))
                    = 1 + (1 + 3)
                    = 1 + 4
                    = 5

Base Cases Are Required

Without a reachable base case, a recursive function keeps calling itself. Python normally stops after about 1,000 nested calls and raises a RecursionError.

Recursive Sum

Consider a finite sequence of numbers \(a_1,a_2,\ldots,a_N\). The sum of these numbers is

\[ s(N) = \sum_{k=1}^{N} a_k = a_1 + a_2 + \cdots + a_N. \]

For \(n \geq 2\), the sum of the first \(n\) numbers can be written in terms of the sum of the first \(n - 1\) numbers:

\[ s(n) = \sum_{k=1}^{n} a_k = a_n + \sum_{k=1}^{n-1} a_k = a_n + s(n-1). \]

This is a recursive relationship for \(s(n)\). The base case is “the sum of one number is that number,”

\[ s(1) = \sum_{k=1}^{1} a_k = a_1. \]
def recursive_sum(a):
    """Sum the entries of the list `a` recursively."""
    # Base case: s(1) = a_1.
    if len(a) == 1:
        return a[0]

    # Recursive case: s(n) = a_n + s(n - 1).
    return a[-1] + recursive_sum(a[:-1])


print(recursive_sum([4, 2, 8, 6, 7, 3]))
30

The calls made by recursive_sum([4, 2, 8, 6, 7, 3]) unfold as follows.

recursive_sum([4, 2, 8, 6, 7, 3])
    = 3 + recursive_sum([4, 2, 8, 6, 7])
    = 3 + (7 + recursive_sum([4, 2, 8, 6]))
    = 3 + (7 + (6 + recursive_sum([4, 2, 8])))
    = 3 + (7 + (6 + (8 + recursive_sum([4, 2]))))
    = 3 + (7 + (6 + (8 + (2 + recursive_sum([4])))))
    = 3 + (7 + (6 + (8 + (2 + 4))))
    = 3 + (7 + (6 + (8 + 6)))
    = 3 + (7 + (6 + 14))
    = 3 + (7 + 20)
    = 3 + 27
    = 30

Each recursive call removes one term, so recursive_sum() calls itself 5 times before reaching the base case recursive_sum([4]). In general, a list of length \(N\) leads to \(N - 1\) recursive calls.

Quick Check

What is the output of the following code?

def echo(n):
    if n == 0:
        print("base")
    else:
        print("down", n)
        echo(n - 1)
        print("up", n)


echo(3)
Answer
down 3
down 2
down 1
base
up 1
up 2
up 3
  • echo(3) prints down 3, then calls echo(2) and waits for it to finish before printing up 3.

  • In the same way, echo(2) and echo(1) each print on the way down and then wait.

  • echo(0) is the base case: it prints base and returns without making another call.

  • The waiting calls then finish in reverse order: echo(1) prints up 1, then echo(2) prints up 2, then echo(3) prints up 3.

Problem 1

The factorial of a nonnegative integer \(n\) is defined by

\[\begin{split} n! = \begin{cases} 1 & \text{if}~n = 0, \\ n \cdot (n-1)! & \text{if}~n \geq 1. \end{cases} \end{split}\]

In other words, if \(f(n) = n!\), then

\[\begin{split} f(n) = \begin{cases} 1 & \text{if}~n = 0, \\ n \cdot f(n-1) & \text{if}~n \geq 1. \end{cases} \end{split}\]

Write a function named factorial() that accepts a nonnegative integer \(n\) and computes \(n!\) recursively, using the definition above.

Test Cases

print(factorial(0))
print(factorial(7))
print(factorial(30))
1
5040
265252859812191058636308480000000

Iterations

Recall that a forward iteration computes a sequence \(x^{(0)}, x^{(1)}, x^{(2)}, \ldots\) from an update rule

\[ x^{(k+1)} = f(x^{(k)}), \]

with \(x^{(0)}\) defined. Forward iteration asks: “given the answer at step \(k\), what is the answer at step \(k + 1\)?”

Recursion uses the same rule written as \(x^{(k)} = f(x^{(k-1)})\). To find \(x^{(k)}\), first find \(x^{(k-1)}\), which requires \(x^{(k-2)}\), and so on back to the base case \(x^{(0)}\). The following code computes the iterates of

\[ x^{(k+1)} = \frac{1}{2}x^{(k)} + 3, \qquad x^{(0)} = 1 \]

both ways.

def iterate_forward(N):
    """Compute x^(N) for x^(k+1) = x^(k) / 2 + 3, x^(0) = 1, with a loop."""
    x = 1  # x^(0).
    for k in range(N):
        x = x / 2 + 3  # x^(k+1) from x^(k).
    return x


def iterate_recursive(k):
    """Compute x^(k) for x^(k) = x^(k-1) / 2 + 3, x^(0) = 1, recursively."""
    if k == 0:  # Base case: x^(0) = 1.
        return 1
    return iterate_recursive(k - 1) / 2 + 3  # Recursive case.


print(iterate_forward(10))
print(iterate_recursive(10))
5.9951171875
5.9951171875

Problem 2

Consider the iteration

\[ x^{(k+1)} = \frac{1}{1 + x^{(k)}}, \qquad x^{(0)} = \alpha \]

for some number \(\alpha\). This iteration produces a continued fraction, for example,

\[ x^{(3)} = \cfrac{1}{1 + \cfrac{1}{1 + \cfrac{1}{1 + \alpha}}}. \]

The value \(x^{(n)}\) can be computed iteratively or recursively.

  • Write a function named continued_fraction_iterative() that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) using a for loop.

  • Write a function named continued_fraction_recursive() that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) without a for loop by using recursion.

Both functions should return \(x^{(N)}\).

Test Cases

As \(k\) increases, the iterates approach \((\sqrt{5} - 1)/2 \approx 0.618\).

print(continued_fraction_iterative(1, 0))
print(continued_fraction_iterative(1, 1))
print(continued_fraction_iterative(1, 2))
print(continued_fraction_iterative(1, 10))
1
0.5
0.6666666666666666
0.6180555555555556
print(continued_fraction_recursive(1, 0))
print(continued_fraction_recursive(1, 1))
print(continued_fraction_recursive(1, 2))
print(continued_fraction_recursive(1, 10))
1
0.5
0.6666666666666666
0.6180555555555556
print(continued_fraction_iterative(10, 27))
print(continued_fraction_recursive(10, 27))
0.6180339887405341
0.6180339887405341