Fibonacci complexity

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:

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

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.

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

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.

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

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