Python Recursion and Iterative Conversion

Recursion is a way of expressing “solve this in terms of a smaller version of itself.” It’s elegant on paper, but in Python it costs real stack frames (the previous lesson) and, done naively, can recompute the same work over and over. This lesson closes Phase 1 by making recursion concrete: how to write it correctly, when it’s wasteful, and how to convert it to iteration.

What you’ll learn

Base case vs recursive case — the two parts every recursive function needs.
Why naive recursive Fibonacci does exponential work.
Converting recursion to iteration with an explicit stack.
Instant memoization with functools.lru_cachefunctools.lru_cache.
Why Python has no tail-call optimization, and what that means for you.

Base case and recursive case

Every correct recursive function needs exactly two parts: a base case that stops the recursion, and a recursive case that makes progress toward it.

base_recursive_case.py

def factorial(n):
    if n <= 1:                  # base case: stops the recursion
        return 1
    return n * factorial(n - 1) # recursive case: smaller subproblem
 
print(factorial(6))

base_recursive_case.py

def factorial(n):
    if n <= 1:                  # base case: stops the recursion
        return 1
    return n * factorial(n - 1) # recursive case: smaller subproblem
 
print(factorial(6))

Miss the base case (or never actually shrink toward it) and you get infinite recursion — which in Python surfaces as a RecursionErrorRecursionError once the stack limit from the previous lesson is hit.

The cost of naive recursion: Fibonacci

$fib(n) = fib(n-1) + fib(n-2)$ looks harmless, but each call branches into two more calls, and many of those calls compute the exact same subproblem repeatedly.

diagram Recursion tree for naive fib(5) — note the repeated subtrees mermaid

  graph TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    D --> F["fib(2)"]
    D --> G["fib(1)"]
    C --> H["fib(2)"]
    C --> I["fib(1)"]

fib(3)fib(3) shows up twice, fib(2)fib(2) shows up three times — and that duplication compounds as nn grows, giving naive Fibonacci $O(2^n)$ time.

naive_fib.py

call_count = 0
 
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
print("fib(20) =", fib(20))
print("calls made:", call_count)   # grows exponentially with n

naive_fib.py

call_count = 0
 
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
print("fib(20) =", fib(20))
print("calls made:", call_count)   # grows exponentially with n

Converting recursion to iteration with an explicit stack

Any recursive function can be rewritten iteratively by managing your own stack (a plain listlist) instead of relying on Python’s call stack — useful both for speed and to sidestep the recursion limit entirely.

iterative_factorial.py

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
 
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):     # a simple loop replaces the call stack
        result *= i
    return result
 
def factorial_explicit_stack(n):
    stack = []
    while n > 1:
        stack.append(n)           # push, mimicking a recursive call
        n -= 1
    result = 1
    while stack:
        result *= stack.pop()     # pop, mimicking the return + multiply
    return result
 
print(factorial_recursive(6), factorial_iterative(6), factorial_explicit_stack(6))

iterative_factorial.py

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
 
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):     # a simple loop replaces the call stack
        result *= i
    return result
 
def factorial_explicit_stack(n):
    stack = []
    while n > 1:
        stack.append(n)           # push, mimicking a recursive call
        n -= 1
    result = 1
    while stack:
        result *= stack.pop()     # pop, mimicking the return + multiply
    return result
 
print(factorial_recursive(6), factorial_iterative(6), factorial_explicit_stack(6))

All three give the same answer; the last two use $O(1)$ (loop) or $O(n)$ (explicit stack list, but no Python call stack) auxiliary space instead of $O(n)$ Python stack frames.

Memoization with functools.lru_cache

Recursion’s repeated-work problem often has a one-line fix: cache each input’s result the first time it’s computed, and reuse it instead of recomputing.

memo_fib.py

from functools import lru_cache
import time
 
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
n = 28
 
start = time.perf_counter()
naive_result = fib_naive(n)
naive_time = time.perf_counter() - start
 
start = time.perf_counter()
memo_result = fib_memo(n)
memo_time = time.perf_counter() - start
 
print(f"naive fib({n}) = {naive_result}, took {naive_time:.4f}s")
print(f"memo  fib({n}) = {memo_result}, took {memo_time:.6f}s")
print("memoization cuts fib from exponential-time to O(n) — same recursive code, one decorator")

memo_fib.py

from functools import lru_cache
import time
 
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
n = 28
 
start = time.perf_counter()
naive_result = fib_naive(n)
naive_time = time.perf_counter() - start
 
start = time.perf_counter()
memo_result = fib_memo(n)
memo_time = time.perf_counter() - start
 
print(f"naive fib({n}) = {naive_result}, took {naive_time:.4f}s")
print(f"memo  fib({n}) = {memo_result}, took {memo_time:.6f}s")
print("memoization cuts fib from exponential-time to O(n) — same recursive code, one decorator")

No tail-call optimization

Some languages (Scheme, Haskell, and others) detect when a recursive call is the very last thing a function does and rewrite it into a loop internally, using constant stack space no matter how deep the recursion goes.

CPython deliberately does not do this. Every recursive call — tail position or not — adds a real stack frame, counted against the recursion limit from the previous lesson.

Practice

Drill 1 — the base case. Complete a recursive sum over a list; the base case is the empty list.

Drill 2 — convert to iteration. Rewrite the same sum with a plain loop instead of recursive calls.

Drill 3 — memoize it. Add the missing import so lru_cachelru_cache can decorate a recursive Fibonacci.

Recap

Every recursive function needs a base case (stops it) and a recursive case (progresses toward it).
Naive recursive Fibonacci is $O(2^n)$ because it recomputes identical subproblems many times over.
Any recursion can be rewritten iteratively with an explicit stack, or sped up instantly with functools.lru_cachefunctools.lru_cache.
CPython has no tail-call optimization — recursion depth always costs real stack frames, no matter how it’s written.

Next: Phase 2 — Python for DSA & CP, starting with how Python’s built-in containers actually store data and why that decides Accepted vs TLE.

If this helped you, consider buying me a coffee ☕

Buy me a coffee