Understanding Recursion & the Call Stack

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Module 3, Chapter 6: Choosing the Right Algorithm Time to complete: ~25 minutes

What Is Recursion?
Base Case and Recursive Case
Tracing the Call Stack
Stack Overflow and Python's Recursion Limit
Space Complexity of Recursion, Revisited
Summary & Next Steps

1. What Is Recursion?

A function is recursive when it calls itself to solve a smaller version of the same problem, until the problem is small enough to answer directly. It's a way of expressing "solve this by solving a smaller version of this" directly in code.

def factorial(n):
    if n == 0:                    # smallest version of the problem
        return 1
    return n * factorial(n - 1)   # solve a smaller version, then use it

factorial(4) doesn't compute 4! in one step — it asks "what is factorial(3)?", multiplies the answer by 4, and returns. factorial(3) does the same thing one level down, and so on.

2. Base Case and Recursive Case

Every correct recursive function needs exactly two things:

Base case — the smallest input(s) the function can answer directly, without recursing. This is what stops the recursion.
Recursive case — how to reduce a bigger problem to a smaller one, and combine that smaller answer into the final result.

def factorial(n):
    if n == 0:                    # BASE CASE — stops the recursion
        return 1
    return n * factorial(n - 1)   # RECURSIVE CASE — smaller problem + combine

Forgetting the base case, or writing a recursive case that never reaches it, causes infinite recursion — Python will eventually raise a RecursionError (Section 4).

3. Tracing the Call Stack

Every function call — recursive or not — is placed on the call stack, a stack of "in-progress" calls (stacks are formalized in Module 5, but the LIFO idea — last in, first out — is exactly what's happening here). Each call waits for the ones below it to finish before it can finish itself.

Calling factorial(4):

factorial(4) calls factorial(3) calls factorial(2) calls factorial(1) calls factorial(0)
                                                                          │
                                                                    returns 1
                                                              │
                                                    1 * 1 = 1  (factorial(1) returns 1)
                                                │
                                      2 * 1 = 2  (factorial(2) returns 2)
                            │
                  3 * 2 = 6  (factorial(3) returns 6)
        │
4 * 6 = 24  (factorial(4) returns 24)

Notice the shape: calls grow downward (each one waits on the next) until the base case is hit, then unwind upward (each waiting call finally computes its result and returns). Nothing is "returned early" — every one of those 5 calls sits on the stack, fully in memory, until the base case resolves and the unwinding begins.

4. Stack Overflow and Python's Recursion Limit

Because each recursive call stays on the stack until it returns, a recursion that goes too deep runs out of stack space. Python protects against this with a recursion limit rather than letting the program crash silently:

import sys
 
print(sys.getrecursionlimit())   # 1000, by default
 
def count_down(n):
    if n == 0:
        return
    count_down(n - 1)
 
count_down(2000)   # raises RecursionError: maximum recursion depth exceeded

You can raise the limit with sys.setrecursionlimit(n), but treat that as a last resort, not a fix — if a recursive solution needs thousands of stack frames, an iterative rewrite (Chapter 2) is usually the right move, not a bigger limit.

5. Space Complexity of Recursion, Revisited

Module 1, Chapter 4 introduced this idea with sum_to_n — worth restating now that you've traced a call stack directly: every unfinished recursive call occupies stack memory, even though no list, dict, or other explicit structure was created.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)
    # Time:  O(n)  — n calls, O(1) work each
    # Space: O(n)  — n calls sitting on the stack at the deepest point

This is the recursive analogue of the nested-loop rule from Module 1, Chapter 3: just as nested loops multiply time complexity, nested (recursive) calls accumulate space complexity, one stack frame per call, until the base case is reached.

6. Summary & Next Steps

Key Takeaways

A recursive function needs a base case (stops recursion) and a recursive case (reduces to a smaller problem).
The call stack grows one frame per call until the base case, then unwinds, computing results on the way back up.
Python raises RecursionError past its recursion limit (default 1000) — treat deep recursion as a design smell, not something to patch with sys.setrecursionlimit.
Recursive calls cost O(depth) stack space, on top of whatever time complexity the algorithm has — this was previewed in Module 1, Chapter 4, and now you've seen exactly why.

Concept Check

What happens if a recursive function has a recursive case but no base case?
In the factorial(4) trace, which call is the last to start, and the first to finish?
Why does factorial(n) have O(n) space complexity even though it never creates a list or dict?

Next Chapter

→ Chapter 2: Recursive Thinking & Recursion Trees

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index