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
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
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:
This is a recursive relationship for \(s(n)\). The base case is “the sum of one number is that number,”
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)printsdown 3, then callsecho(2)and waits for it to finish before printingup 3.In the same way,
echo(2)andecho(1)each print on the way down and then wait.echo(0)is the base case: it printsbaseand returns without making another call.The waiting calls then finish in reverse order:
echo(1)printsup 1, thenecho(2)printsup 2, thenecho(3)printsup 3.
Problem 1
The factorial of a nonnegative integer \(n\) is defined by
In other words, if \(f(n) = n!\), then
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
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
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
for some number \(\alpha\). This iteration produces a continued fraction, for example,
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 aforloop.Write a function named
continued_fraction_recursive()that accepts a number \(\alpha\) and a nonnegative integer \(N\). Compute \(x^{(N)}\) without aforloop 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