🎓 A1Learner
🔍

DSA Recursion and the Fibonacci Trap

Fibonacci numbers form a sequence where each number adds the two numbers before it. The Fibonacci trap is the repeated work inside a plain recursive Fibonacci function.

The loop version counts its steps

A loop builds the sequence in order, one new value per step. The step count for the tenth value is just ten.

def fib_loop(n):
    a = 0
    b = 1
    steps = 0
    for _ in range(n):
        a, b = b, a + b
        steps += 1
    return a, steps

print(fib_loop(10))

The recursive version counts its calls

Naive here means the plain version that calls itself twice with no stored answers. The counter inside shows how fast the calls pile up.

def fib(n, counter):
    counter[0] += 1
    if n < 2:
        return n
    return fib(n - 1, counter) + fib(n - 2, counter)

for n in [5, 8, 10]:
    counter = [0]
    print(n, fib(n, counter), "calls:", counter[0])

The same values solved again and again

The tally counts how many times each smaller value gets solved in one run. Small values near the bottom are solved over and over.

def fib(n, tally):
    tally[n] = tally.get(n, 0) + 1
    if n < 2:
        return n
    return fib(n - 1, tally) + fib(n - 2, tally)

tally = {}
fib(6, tally)
for key in sorted(tally):
    print("fib(" + str(key) + ") solved", tally[key], "times")

Example

def fib_naive(n, counter):
    counter[0] += 1
    if n < 2:
        return n
    return fib_naive(n - 1, counter) + fib_naive(n - 2, counter)

def fib_loop(n):
    a = 0
    b = 1
    steps = 0
    for _ in range(n):
        a, b = b, a + b
        steps += 1
    return a, steps

for n in [10, 15, 20]:
    counter = [0]
    value = fib_naive(n, counter)
    loop_value, loop_steps = fib_loop(n)
    print("n =", n, "value:", value, "naive calls:", counter[0], "loop steps:", loop_steps)

Key points

  • A naive Fibonacci function calls itself twice for every value above one.
  • The call count grows far faster than the answer needs it to.
  • A loop solves each Fibonacci value once, in order.
  • Memoisation is storing each answer so a repeated call can reuse it.

In this example, the naive function and the loop compute the same three Fibonacci values. At n equal to 20, the loop needs 20 steps, one per value. The naive function needs 21891 calls for that same value. Each rise of five in n multiplies the call count by more than ten. Memoisation is named here as the cure, and the dynamic programming entry teaches it in full.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Naive Fibonacci makes 177 calls to solve n equal to 10. What happens to the call count as n keeps growing?