Recursion Practice — Factorial, Fibonacci, Powers

By the end of this lesson you can:

• Write factorial, fibonacci, and power recursively.
• Read the equivalent iterative loop and pick the right one for the job.
• Spot exponential time blow-up in naïve fibonacci.
• Cache repeated subproblems with functools.lru_cache.

# Iterative
def factorial_loop(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

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

print(factorial(5))         # 5*4*3*2*1 = 120
print(factorial_loop(5))    # same

Same answer. Same speed. For factorial, both are fine — pick whichever reads better.

1 · Factorial — a clean linear recursion

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

One call per step. n deep. factorial(1000) hits Python's recursion limit; for big factorials the loop wins.

2 · Fibonacci — branching recursion

# Naïve
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(10))           # 55
print(fib(35))           # 9227465  -- but this took seconds!

For fib(35), the function calls itself ~30 million times. Why? Each call branches into two. fib(35) calls fib(34) and fib(33); fib(34) also calls fib(33); both fib(33)s recompute everything from scratch. Exponential blow-up.

Fix #1 · Iterative Fibonacci

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

print(fib_loop(100))     # 354224848179261915075   -- instant!

No branching. One pass. fib_loop(100) is milliseconds.

Fix #2 · Memoised recursion

Keep the recursive shape; cache results. functools.lru_cache does it in one decorator.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

print(fib_memo(100))    # 354224848179261915075   -- also instant

lru_cache remembers every (args) → result pair. The second time fib_memo(33) is called, it returns instantly from the cache. The exponential blow-up vanishes.

3 · Power — divide and conquer

# Naïve recursion — linear in n
def power(base, n):
    if n == 0:
        return 1
    return base * power(base, n - 1)

# Smart — divide and conquer
def fast_power(base, n):
    if n == 0:
        return 1
    if n % 2 == 0:
        half = fast_power(base, n // 2)
        return half * half
    return base * fast_power(base, n - 1)

print(power(2, 10))         # 1024
print(fast_power(2, 10))    # 1024
print(fast_power(2, 1000))  # huge — works fine

Naïve power(2, 1000) needs 1000 recursive calls. fast_power needs only ~10 (each step roughly halves n). Divide-and-conquer turns linear into logarithmic.

The big lesson

Problem                Naïve recursion   Better
factorial(n)           O(n)              same as loop
fib(n) naïve           O(2ⁿ) — bad!     O(n) with memo or loop
power(b, n)            O(n)              O(log n) with halving

Recursion is a tool. Use the right shape for the problem.

The recursion limit

import sys
print(sys.getrecursionlimit())     # default ~1000
sys.setrecursionlimit(10_000)      # raise it if you really need to

If you need more than 10k deep, you almost certainly want iteration instead. Python is not optimised for deep recursion (no tail-call optimisation).

Save as recursion_bench.py:

# recursion_bench.py — race naïve vs smart for each classic

import time
from functools import lru_cache


# --- Factorial ---

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

def factorial_loop(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r


# --- Fibonacci ---

def fib_naive(n):
    if n < 2: return n
    return fib_naive(n - 1) + fib_naive(n - 2)

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2: return n
    return fib_memo(n - 1) + fib_memo(n - 2)

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


# --- Power ---

def power(base, n):
    if n == 0: return 1
    return base * power(base, n - 1)

def fast_power(base, n):
    if n == 0: return 1
    if n % 2 == 0:
        h = fast_power(base, n // 2)
        return h * h
    return base * fast_power(base, n - 1)


# --- Bench ---

def time_call(fn, *args, label=""):
    start = time.perf_counter()
    result = fn(*args)
    elapsed = time.perf_counter() - start
    print(f"  {label:<22} {elapsed * 1000:>8.3f} ms  → {str(result)[:50]}...")


print("=== factorial(100) ===")
time_call(factorial,      100, label="recursive")
time_call(factorial_loop, 100, label="iterative")

print("\n=== fibonacci(30) ===")
time_call(fib_naive, 30, label="naive recursion")
time_call(fib_memo,  30, label="memoised")
time_call(fib_loop,  30, label="iterative")

print("\n=== fibonacci(35) — naive only ===")
time_call(fib_naive, 35, label="naive recursion")    # noticeably slower!

print("\n=== power(2, 100) ===")
time_call(power,       2, 100, label="naive recursion")
time_call(fast_power,  2, 100, label="divide-and-conquer")

Sample output (times will vary)

=== factorial(100) ===
  recursive                 0.060 ms  → 93326215443944152681699238856266700490715968264381...
  iterative                 0.018 ms  → 93326215443944152681699238856266700490715968264381...

=== fibonacci(30) ===
  naive recursion         210.000 ms  → 832040
  memoised                  0.020 ms  → 832040
  iterative                 0.005 ms  → 832040

=== fibonacci(35) — naive only ===
  naive recursion        2200.000 ms  → 9227465

=== power(2, 100) ===
  naive recursion           0.045 ms  → 1267650600228229401496703205376
  divide-and-conquer        0.008 ms  → 1267650600228229401496703205376

Read the diff

Factorial: same speed either way. Fibonacci naïve is millions of times slower than memo or loop. Power doubling is ~6x faster — and the gap widens with bigger exponents. Three different lessons from three classic functions.

Three classic recursive functions. Factorial is a clean linear recursion — same as a loop. Fibonacci naïve is exponentially slow because it recomputes overlapping subproblems; @lru_cache fixes it. Power can be sped up dramatically with divide-and-conquer halving — from O(n) to O(log n). The pattern: any recursion that revisits subproblems benefits hugely from memoisation; any recursion that can split a problem in half benefits from divide-and-conquer.