AI Hints
DSA in Python · Lesson 41 of 132

The Call Stack

How Python keeps track.

⏱ 2 min read▶ Video at 47:27🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

When a function calls another function, Python has to remember where it was, so it can come back later. It keeps those notes on a stack, called the call stack. Recursion simply puts many calls on that stack at once.

The Call Stack
From the video: The Call Stack
  • Python must remember where it was
  • Notes on a stack
  • Recursion stacks many calls

Watching the stack

We add a depth argument, and indent each line to show how deep we are. Every call goes one level deeper, and waits. When the base case returns, the waiting calls finish in reverse order, last in, first out. Run it. You can see the calls stack up, and then unwind.

stack_trace.pypython
def factorial(n, depth=0):
    pad = "  " * depth
    print(f"{pad}factorial({n}) called")
    if n <= 1:
        result = 1
    else:
        result = n * factorial(n - 1, depth + 1)
    print(f"{pad}factorial({n}) returns {result}")
    return result

factorial(4)
Output
factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

The cost of recursion

Every waiting call uses a little memory on the call stack. So recursion that goes N levels deep uses O of N space, even if it looks like it uses nothing. And Python limits how deep the stack can go, to about a thousand calls by default.

keyvalue
Each calla frame on the stack
Unwindinglast in, first out
Depth nO(n) space
Default limitabout 1000 calls

Summary

The call stack holds every waiting call, and unwinds last in, first out. Deep recursion uses memory. Next, what happens when recursion goes wrong.

Key takeaways
  • Calls wait on a stack
  • Unwind in reverse
  • Depth costs memory
Next up: Base Cases — and when recursion goes wrong