Editor

Fibonacci with recursion in Python

Each Fibonacci number is the sum of the two before it, so a recursive function calls itself twice. That repeats the same work many times, and memoization fixes it by remembering every answer.

The arrow keys step through it. Edit the code to try your own input.

How it works

  1. fib(n) returns fib(n - 1) + fib(n - 2). fib(0) and fib(1) are the base cases.
  2. Both calls split again, so the number of calls grows very fast as n grows.
  3. The same values are worked out again and again: fib(3) runs twice and fib(2) three times, 15 calls in all.
  4. fib_memo saves each answer in the dictionary memo, so every value is worked out once and later calls just look it up: 9 calls instead of 15.
  5. Plain recursion takes O(2ⁿ) time. With memoization it takes O(n).

What to watch

  • Watch calls in the global frame climb to 15 for the plain version.
  • Watch fib(5) call fib(3) again, after fib(4) has already worked it out once.
  • Watch memo fill up from memo[2] upwards, and then fib_memo(2, memo) and fib_memo(3, memo) return at once from the dictionary.

The code

calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n                 # fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2)

def fib_memo(n, memo):
    if n in memo:
        return memo[n]           # worked out before: just look it up
    if n < 2:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

print("fib(5) =", fib(5), "after", calls, "calls")
memo = {}
print("fib_memo(5) =", fib_memo(5, memo), "memo:", memo)
Output
fib(5) = 5 after 15 calls
fib_memo(5) = 5 memo: {2: 1, 3: 2, 4: 3, 5: 5}

Open it in the editor · Python Program to Print the Fibonacci Series Using Recursion, explained