Recursive Fibonacci

Write a recursive Fibonacci function.

Base case

Fibonacci has two base cases: F(0) = 0 and F(1) = 1. These two values are known directly and stop the recursion.

Having two base cases ensures the function always terminates. Each call decreases n and eventually reaches 0 or 1.

Naive recursive Fibonacci has complexity O(2^n). This is exponential growth because each call makes two sub-calls.

For n=40, billions of calls are made. This shows why naive recursion is slow. Memoization solves this problem.

Write fib_small(n). If n=0 return 0, if n=1 return 1. Print 1 with print(fib_small(1)).

Show example solution

def fib_small(n):
    # Small Fibonacci
    if n == 0:
        return 0
    if n == 1:
        return 1
print(fib_small(1))

Next lesson: Call tree