Recursion and the Call Stack

Recursion is a function calling itself to solve a smaller version of the same problem. It is the natural language for trees, graphs, divide-and-conquer sorting, and backtracking, so mastering it now pays off in every remaining lesson. The trick is learning to trust the recursive leap: define the base case, make the problem smaller, and let the call stack do the bookkeeping.

What You'll Learn

• The two ingredients of every recursion: base case and smaller subproblem
• How the call stack executes recursive calls
• Why naive recursion can be exponentially slow, and how memoization fixes it
• When to choose recursion vs iteration

The Anatomy of a Recursive Function

Every correct recursive function has a base case (where it stops) and a recursive case (where it calls itself on a smaller input):

factorial(5) becomes 5 * factorial(4), which becomes 5 * 4 * factorial(3), and so on down to the base case. Each pending call waits on the call stack (the same stack structure from two lessons ago) until its subproblem returns.

Watching the Stack

Add prints at each depth and the stack becomes visible:

Notice the shape: all the enter lines, then the base case, then the leave lines unwind in reverse order. That unwinding is the stack popping. Python limits stack depth (about 1000 frames by default), so recursion suits problems whose depth stays modest, like trees, rather than million-step loops.

Recursion Meets Data: Summing Nested Lists

Recursion shines when the data itself is nested. A loop struggles with arbitrarily deep nesting; recursion handles it naturally:

The Fibonacci Trap and Memoization

Naive recursive Fibonacci recomputes the same values over and over, giving O(2^n) time. Memoization caches results so each subproblem is solved once, collapsing it to O(n). This is your first taste of dynamic programming. Run it fullscreen and compare the call counts:

Over 240,000 calls for fib_naive(25), versus 26 subproblems for the memoized version. The @lru_cache decorator is the one-line professional way to memoize; writing the cache dict by hand (as in the exercise below) shows you what it does.

Recursion vs Iteration

Anything recursive can be rewritten with an explicit stack, and vice versa. Practical guidance:

• Use recursion when the problem is self-similar: trees, nested data, divide and conquer, backtracking
• Use iteration for simple linear passes; it is faster and cannot overflow the stack
• If a recursion only calls itself once at the end (like countdown), a loop is usually cleaner in Python

Exercises

Key Takeaways

• Every recursion needs a base case and a strictly smaller subproblem
• The call stack tracks pending calls; deep recursion can hit Python's stack limit
• Recursion fits self-similar problems: trees, nested data, divide and conquer
• Naive recursion with overlapping subproblems explodes exponentially; memoization (@lru_cache) makes each subproblem cost O(1) after the first time
• Trust the recursive leap: assume the smaller call works, and combine its result