Factorial and Fibonacci

The Idea

Factorial recurses once per step, so its calls form a straight line n frames deep and cost O(n). Naive Fibonacci recurses twice, so the calls fan out into a tree and the same subproblems get solved over and over — roughly O(2^n).

Real-World Example

An office where anyone handed a report splits it into two smaller reports and passes them to two colleagues. Nobody compares notes, so the same tiny report ends up written dozens of times across the building.

The Code

def factorial(n):
    if n <= 1:                       # base case
        return 1
    return n * factorial(n - 1)      # one branch: a straight line

def fib(n):
    if n < 2:
        return n                     # fib(0) = 0, fib(1) = 1
    return fib(n - 1) + fib(n - 2)   # two branches: a tree

print(factorial(5))   # 120
print(fib(10))        # 55

def factorial(n):
  if n <= 1:
      return ___
  return n * factorial(n - 1)

print(factorial(4))   # should print 24