This post mentions some practical considerations for using recursion to solve problems. Most of the material is summarized from the Section 1.2 of the following book:
Harold Abelson and Gerald Jay Sussman with Julie Sussman. Structure and Interpretation of Computer Programs (SICP), Second edition. The MIT Press, 1996. websiteYou can refer to this book for more detailed discussion of the topic. Python examples are derived from Scheme versions found in this book. Scheme language guarantees optimization of tail calls in the language specification like most functional programming languages. On the other hand, Python language is a representative for mainstream languages in which this optimization is neither guaranteed nor performed.
Linear Recursion
A factorial function can be written in recursive form as follows:
; Scheme
(define (fact n)
(if (= n 1)
1
(* n (fact (- n 1)))))
# Python
def fact(n):
if n == 0:
return 1
else:
return n * fact(n - 1)
Evaluation of this calculation is as follows:
; Scheme
(fact 5)
(fact 4)
(fact 3)
(fact 2)
(fact 1)
(fact 0)
1
1
2
6
24
120
# Python
fact(5)
fact(4)
fact(3)
fact(2)
fact(1)
fact(0)
1
1
2
6
24
120
Note, function call stack grows in both languages, meaning that one can get a stack overflow error with a big enough argument. We can instead write the function in tail recursive form as an iterative process as follows:
; Scheme
(define (fact n)
(fact-iter 1 1 n))
(define (fact-iter acc counter max-count)
(if (> counter max-count)
acc
(fact-iter (* counter acc)
(+ counter 1)
max-count)))
# Python
def fact(n):
return fact_iter(1, 1, n)
def fact_iter(acc, counter, max_count):
if counter > max_count:
return acc
else:
return fact_iter(counter * acc,
counter + 1,
max_count)
Evaluation of this calculation is as follows:
; Scheme
(fact 5)
(fact-iter 1 1 5)
(fact-iter 1 2 5)
(fact-iter 2 3 5)
(fact-iter 6 4 5)
(fact-iter 24 5 5)
(fact-iter 120 6 5)
120
# Python
fact(5)
fact_iter(1, 1, 5)
fact_iter(1, 2, 5)
fact_iter(2, 3, 5)
fact_iter(6, 4, 5)
fact_iter(24, 5, 5)
fact_iter(120, 6, 5)
120
120
120
120
120
120
120
In this case, function call stack still grows in Python but not in Scheme. This is due to tail call optimization performed in Scheme to avoid deferred function calls when they are at tail positions. On the other hand, a more idiomatic way to write an iterative factorial function in Python is as follows:
# Python
def fact(n):
acc = 1
for i in range(1, n + 1):
acc *= i
return acc
In this form, there is only a single function call so the call stack does not grow.
Tree Recursion
A fibonacci function can be written in recursive form as follows:
; Scheme
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
# Python
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n - 1) + fib(n - 2)
Evaluation of this calculation is as follows:
; Scheme
(fib 5)
(fib 4)
(fib 3)
(fib 2)
(fib 1)
1
(fib 0)
0
1
(fib 1)
1
2
(fib 2)
(fib 1)
1
(fib 0)
0
1
(fib 1)
1
3
(fib 3)
(fib 2)
(fib 1)
1
(fib 0)
0
1
(fib 1)
1
2
5
# Python
fib(5)
fib(4)
fib(3)
fib(2)
fib(1)
1
fib(0)
0
1
fib(1)
1
2
fib(2)
fib(1)
1
fib(0)
0
1
fib(1)
1
3
fib(3)
fib(2)
fib(1)
1
fib(0)
0
1
fib(1)
1
2
5
Note, same calculations occur at multiple points in the tree, meaning that the computation is not efficient and it may not finish with a big enough argument. We can instead write the function in tail recursive form as an iterative process as follows:
; Scheme
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b counter)
(if (= counter 0)
b
(fib-iter (+ a b) a (- counter 1))))
# Python
def fib(n):
return fib_iter(1, 0, n)
def fib_iter(a, b, counter):
if counter == 0:
return b
else:
return fib_iter(a + b, a, counter - 1)
Evaluation of this calculation is as follows:
; Scheme
(fib 5)
(fib-iter 1 0 5)
(fib-iter 1 1 4)
(fib-iter 2 1 3)
(fib-iter 3 2 2)
(fib-iter 5 3 1)
(fib-iter 8 5 0)
5
# Python
fib(5)
fib_iter(1, 0, 5)
fib_iter(1, 1, 4)
fib_iter(2, 1, 3)
fib_iter(3, 2, 2)
fib_iter(5, 3, 1)
fib_iter(8, 5, 0)
5
5
5
5
5
5
5
Similarly in this case, function call stack still grows in Python but not in Scheme. On the other hand, a more idiomatic way to write an iterative fibonacci function in Python is as follows:
# Python
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
In this form, there is only a single function call so the call stack does not grow.
Dynamic Programming
Factorial and fibonacci examples are easily implemented as iterative calculations. However, we may not always be able to convert all problems to such an explicit iterative form in general. For example, dynamic programming requires dividing the original problem into simpler sub-problems in a recursive manner. There are two common techniques used in dynamic programming to avoid repetitive calculations for efficiency namely memoization and tabulation. Next we demonstrate these techniques over the fibonacci example and then use them to solve a more complicated problem.
Memoization
Memoization involves caching calculated results in a lookup table to avoid doing same calculations multiple times. This strategy is a top-down approach starting from the original problem to divide it into smaller problems. A memoized fibonacci function in Python can be written as follows:
# Python
def fib(n, memo={}):
if n == 0:
return 0
elif n == 1:
return 1
elif n in memo:
return memo[n]
else:
f = fib(n - 1) + fib(n - 2)
memo[n] = f
return f
Or more simply using functools.lru_cache decorator from the standard library:
# Python
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
In this form, each fibonacci number is only calculated once at most.
Tabulation
Memoized functions still keep the recursive structure in the definition but avoid doing same calculations multiple times for tree recursive algorithms. Since the calculations are still performed recursively, function call stack can grow large with big arguments to result in a stack overflow error. One may need to use tabulation to avoid such problems. In this approach, one allocates a table for each possible values of the arguments and then fills this table in an appropriate order. This strategy is a bottom-up approach starting from smaller problems to solve the original problem. A tabulated fibonacci function in Python can be written as follows:
# Python
def fib(n):
table = [0 for i in range(n + 1)]
table[0] = 0
table[1] = 1
for i in range(2, n + 1):
table[i] = table[i - 1] + table[i - 2]
return table[n]
In this form, each fibonacci number is only calculated once. Note, consecutive calls to this function reinitializes the table from the start, though this can also be eliminated by using a global table instead.
Coin Change Problem
Fibonacci is a trivial example which makes it difficult to see how these techniques can be useful in practice. Instead, consider the following problem given in the Section 1.2.2 of the book:
How many different ways can we make change of $1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to change any given amount of money?
This problem has a simple recursive solution using the following observation provided in the book:
The number of ways to change amount a using n kinds of coins equals; (1) the number of ways to change amount a using all but the first kind of coin, plus (2) the number of ways to change amount a - d using all n kinds of coins, where d is the denomination of the first kind of coin.
Using this observation, the solution provided for this problem in the book is as follows:
; Scheme
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(cond ((= amount 0) 1)
((or (< amount 0) (= kinds-of-coins 0)) 0)
(else (+ (cc amount
(- kinds-of-coins 1))
(cc (- amount
(first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
A rough Python translation of this solution is as follows:
# Python
coins = [1, 5, 10, 25, 50]
def count(amount):
return count_iter(amount, len(coins))
def count_iter(amount, kinds):
if amount == 0:
return 1
elif amount < 0 or kinds == 0:
return 0
else:
c1 = count_iter(amount, kinds-1)
c2 = count_iter(amount - coins[kinds-1], kinds)
return c1 + c2
We can then solve the original problem as follows:
# Python
print(count(100)) # 292
When we increase the amount to 5.00$ instead, the computation starts to choke for a few seconds:
# Python
print(count(500)) # 59576
When we increase the amount to 10.00$, we get a stack overflow:
# Python
print(count(1000)) # RecursionError: maximum recursion depth exceeded in comparison
We can try using memoization strategy for efficiency:
# Python
from functools import lru_cache
coins = [1, 5, 10, 25, 50]
def count_memo(amount):
return count_memo_iter(amount, len(coins))
@lru_cache(maxsize=None)
def count_memo_iter(amount, kinds):
if amount == 0:
return 1
elif amount < 0 or kinds == 0:
return 0
else:
c1 = count_memo_iter(amount, kinds-1)
c2 = count_memo_iter(amount - coins[kinds-1], kinds)
return c1 + c2
When we use memoization, computations are efficient but the stack overflow issue remains:
# Python
print(count_memo(100)) # 292
print(count_memo(500)) # 59576
print(count_memo(1000)) # RecursionError: maximum recursion depth exceeded in comparison
We can instead use tabulation strategy for safety:
# Python
coins = [1, 5, 10, 25, 50]
def count_table(amount):
table = [[0 for i in range(len(coins)+1)] for j in range(amount+1)]
for i in range(len(coins)+1):
table[0][i] = 1
for i in range(1, len(coins)+1):
for j in range(1, amount+1):
c1 = table[j][i-1]
c2 = table[j-coins[i-1]][i] if j >= coins[i-1] else 0
table[j][i] = c1 + c2
return table[amount][len(coins)]
When we use tabulation, computations are efficient and the stack does not overflow:
# Python
print(count_table(100)) # 292
print(count_table(500)) # 59576
print(count_table(1000)) # 801451