Generating the Fibonacci sequence is a classic early exercise in recursion and memoization. The recursive code for generating the sequence could hardly be simpler: it reads just like the definition of the Fibonacci sequence itself.

def fib(n):
return n if n <= 1 else fib(n-1) + fib(n-2)


Then, by memoizing the function and counting the calls it makes to itself, we can see the benefits of memoization.

def fib_rec(n):
fib_rec.counter += 1
return n if n <= 1 else fib_rec(n-1) + fib_rec(n-2)

def fib_memo(n):
fib_memo.counter += 1
if n not in fibs:
fibs[n] = fib_memo(n-1) + fib_memo(n-2)
return fibs[n]

for i in range(11):
fib_rec.counter = 0
fib_memo.counter = 0
fibs = { 0: 0, 1: 1 }
result_rec = fib_rec(i)
result_memo = fib_memo(i)
assert(result_rec == result_memo)
print("fib({}) = {}: Recursive calls: {}, memoized calls: {}"
.format(i, result_rec, fib_rec.counter, fib_memo.counter))


This gives us the following output:

n fib(n) Recursive calls Memoized calls
0 0 1 1
1 1 1 1
2 1 3 3
3 2 5 5
4 3 9 7
5 5 15 9
6 8 25 11
7 13 41 13
8 21 67 15
9 34 109 17
10 55 177 19

The memoized calls number is easy enough to explain: we make n-1 calls that actually require inserting to fibs, plus an additional n calls that just require lookup from fibs, for a total of 2n - 1 calls (0 being a special case requires 0 inserts to fibs, not -1). Accounting for the number of recursive calls is more interesting.

Calling fib_rec(n) involves one initial call, followed by calls to fib(n-1) and fib(n-2), so we can write the number of calls $$\hat{f}(n)$$ as

$\hat{f}(n) = 1 + \hat{f}(n-1) + \hat{f}(n-2)$

The Fibonacci sequence again! For completeness, let’s define our base cases. We know these don’t require any recursive function calls because we put those entries in the lookup table ourselves.

$\hat{f}(0) = 1,\ \hat{f}(1) = 1$

Now, let’s express $$\hat{f}$$, our count of calls required to compute a Fibonacci number, in terms of $$f$$, the Fibonacci sequence itself.

$\hat{f}(n) = 2 f(n+1) - 1$

We should be able to apply this same principle to other recurrence relations. As an example, let’s take the binomial formula in its recursive form.

$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$

We can write a bit of Python to compute the number of calls required to compute various values of this function.

def choose(n, k):
choose.counter += 1
if k == 0 or k == n:
return 1
return choose(n-1, k-1) + choose(n-1, k)

for n in range(11):
for k in range(n+1):
choose.counter = 0
print(choose(n, k), end=' ')
print()

for n in range(11):
for k in range(n+1):
choose.counter = 0
choose(n, k)
print(choose.counter, end=' ')
print()


This gives us two lopsided triangles.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1

1
1 1
1 3 1
1 5 5 1
1 7 11 7 1
1 9 19 19 9 1
1 11 29 39 29 11 1
1 13 41 69 69 41 13 1
1 15 55 111 139 111 55 15 1
1 17 71 167 251 251 167 71 17 1
1 19 89 239 419 503 419 239 89 19 1


The first is Pascal’s triangle, and we second we can see is

$\widehat{\binom{n}{k}} = 2 \binom{n}{k} - 1$

This is remarkably similar to the Fibonacci formula from earlier! Not shocking, perhaps, but satisfying to see.