Visualising the Call Stack
Use Python's sys module and print tracing to observe stack frames growing and shrinking, and understand stack-overflow risks in deep recursion.
Visualising the Call Stack is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is the Call Stack?
Every function call in Python creates a stack frame on the call stack. The frame stores the function's local variables, its return address (where execution resumes after the function returns), and the current instruction pointer. When a function returns, its frame is popped and control passes back to the caller. The call stack grows downward with each call and shrinks with each return.
Understanding the call stack is essential for debugging recursive code, estimating memory usage, and avoiding stack overflow errors in deep recursion.
import traceback
def outer():
inner()
def inner():
# Print the current call stack
traceback.print_stack()
outer()
# Shows: module -> outer -> innerObserving Stack Frames with sys
Python's sys module provides tools to inspect the call stack at runtime. sys._getframe(n) returns the stack frame n levels above the current function. Each frame has a f_locals dict of local variables and f_code.co_name for the function name. Inserting debug prints inside a recursive function reveals how frames accumulate and dissolve.
import sys
def countdown(n):
depth = 0
frame = sys._getframe(0)
while frame:
depth += 1
frame = frame.f_back
print(' ' * (n * 2) + f'countdown({n}) called, stack depth={depth}')
if n <= 0:
return
countdown(n - 1)
print(' ' * (n * 2) + f'countdown({n}) returning')
countdown(3)Tracing Factorial on the Call Stack
Trace factorial(4) on the call stack. Calls accumulate: factorial(4) calls factorial(3) calls factorial(2) calls factorial(1) calls factorial(0). At the base case the stack has 5 frames. Returns unwind: factorial(0) returns 1; factorial(1) returns 1×1=1; factorial(2) returns 2×1=2; factorial(3) returns 3×2=6; factorial(4) returns 4×6=24. The depth equals n+1, the space complexity is O(n).
def factorial(n, indent=0):
prefix = ' ' * indent
print(prefix + f'-> factorial({n})')
if n == 0:
print(prefix + '<- returns 1')
return 1
result = n * factorial(n - 1, indent + 1)
print(prefix + f'<- returns {result}')
return result
factorial(4)Stack Overflow: Python's Recursion Limit
Python raises RecursionError when the call stack exceeds its limit (default ~1000 frames). This protects against infinite recursion consuming all memory. For problems with input size n = 10^4 or more, a recursive solution with O(n) depth will crash without raising the limit. The iterative equivalent has O(1) stack space because it uses only one frame for the enclosing function.
import sys
print('Recursion limit:', sys.getrecursionlimit())
def deep_recursion(n):
if n == 0:
return 0
return 1 + deep_recursion(n - 1)
# Safe: within limit
try:
print(deep_recursion(900))
except RecursionError:
print('Overflow at 900')
# Overflow
try:
print(deep_recursion(2000))
except RecursionError:
print('RecursionError at 2000 — limit exceeded!')Increasing the Recursion Limit
You can increase Python's recursion limit with sys.setrecursionlimit(n), but this is a band-aid. The default limit exists because each stack frame occupies memory (typically several hundred bytes on CPython). Setting the limit to 10^6 and then calling a 10^5-deep recursion can allocate hundreds of megabytes of stack space. The correct fix is usually to convert to an iterative solution or use memoisation to reduce depth.
import sys
# Only increase when you are certain of the maximum depth
# and have confirmed it is safe
original = sys.getrecursionlimit()
sys.setrecursionlimit(5000)
def sum_to(n):
if n == 0:
return 0
return n + sum_to(n - 1)
print(sum_to(3000)) # Works with increased limit
sys.setrecursionlimit(original) # restore
print('Limit restored:', sys.getrecursionlimit())The Call Stack for Mutual Recursion
Mutual recursion is when function A calls function B and function B calls function A. The call stack alternates between frames of A and B. This pattern appears in even/odd number determination and in state-machine simulations. It is correct as long as the stack depth remains bounded — but it can be harder to reason about depth than simple linear recursion.
def is_even(n):
if n == 0:
return True
return is_odd(n - 1)
def is_odd(n):
if n == 0:
return False
return is_even(n - 1)
# Stack alternates: is_even(4)->is_odd(3)->is_even(2)->is_odd(1)->is_even(0)
print(is_even(4)) # True
print(is_odd(5)) # True
print(is_even(7)) # FalseTail Calls and Why Python Doesn't Optimise Them
A tail call is a recursive call that is the last operation before returning — no computation follows it. In languages like Haskell or Scheme, tail calls are optimised into loops (tail call optimisation, TCO), giving O(1) stack space. Python deliberately does not implement TCO. As Guido van Rossum explained, preserving the full stack trace for debugging was more valuable than the space savings. So in Python, tail-recursive code still uses O(n) stack space.
# Tail-recursive factorial (accumulator pattern)
def factorial_tail(n, acc=1):
if n == 0:
return acc
return factorial_tail(n - 1, acc * n) # tail call
# In Python, this still uses O(n) stack space (no TCO)
# But it IS semantically tail-recursive
print(factorial_tail(6)) # 720
print(factorial_tail(10)) # 3628800
# Iterative version: same logic, O(1) stack
def factorial_iter(n):
acc = 1
while n > 0:
acc *= n
n -= 1
return acc
print(factorial_iter(10)) # 3628800Printing Recursion Trees
Visualising the recursion tree helps identify where duplicate sub-problems occur (the target for memoisation). A simple way to print the tree: add an indent parameter that increases by 2 spaces per level. Each call prints its arguments on entry and its return value on exit. Running this for Fibonacci(5) clearly shows the exponential branching and repeated calls.
def fib_traced(n, indent=0):
prefix = ' ' * indent
print(prefix + f'fib({n})')
if n <= 1:
print(prefix + f'=> {n}')
return n
result = fib_traced(n-1, indent+1) + fib_traced(n-2, indent+1)
print(prefix + f'=> {result}')
return result
fib_traced(4)
# Shows the branching tree with duplicated sub-problemsStack Depth = Space Complexity
For any recursive function, the maximum call stack depth equals the maximum recursion depth at any point during execution. This depth directly equals the auxiliary space complexity. For linear recursion (factorial, Fibonacci, reverse string), depth is O(n). For divide-and-conquer algorithms (merge sort, binary search), depth is O(log n). For tree traversals, depth is O(h) where h is the tree height (O(log n) balanced, O(n) worst case).
# Recursion depth = space complexity
# Linear recursion: O(n) stack
def linear_depth(n):
if n == 0: return 0
return 1 + linear_depth(n - 1) # depth = n
# Logarithmic recursion: O(log n) stack
def log_depth(n):
if n <= 1: return 0
return 1 + log_depth(n // 2) # depth = log2(n)
print('n=32 linear depth:', 32)
print('n=32 log depth:', log_depth(32)) # 5
print('n=1024 log depth:', log_depth(1024)) # 10Converting Recursion to Iteration with an Explicit Stack
Any recursive algorithm can be made iterative by managing the call stack explicitly with a Python list. Instead of letting the OS manage frames, you push 'tasks' onto the list and pop them in a loop. This removes Python's recursion limit and reduces per-frame overhead, at the cost of more complex code. The iterative DFS using an explicit stack we saw earlier follows this pattern exactly.
# Recursive inorder traversal -> iterative with explicit stack
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
while curr:
stack.append(curr)
curr = curr.left
curr = stack.pop()
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6))
print(inorder_iterative(root)) # [1, 2, 3, 4, 6]Summary: Call Stack and Space
The call stack is the hidden data structure behind all recursion. Its depth equals the space complexity of your recursive algorithm. Python caps it at ~1000, so algorithms with O(n) recursion depth need either an increased limit (risky) or an iterative rewrite. When writing recursive code in interviews, always state the space complexity due to the call stack: 'This uses O(n) space for the recursion depth' or 'O(log n) for a balanced-tree traversal'.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: each recursive call creates a stack frame holding local variables and the return address, maximum stack depth equals the auxiliary space complexity of the recursion, and Python's recursion limit (~1000) makes algorithms with O(n) depth risky for large n — convert to iterative using an explicit stack. Next up we compare recursive and iterative solutions and discuss when to use each.
Frequently asked questions
Is the “Visualising the Call Stack” lesson free?
Yes — the full text of “Visualising the Call Stack” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Visualising the Call Stack”?
Use Python's sys module and print tracing to observe stack frames growing and shrinking, and understand stack-overflow risks in deep recursion. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Visualising the Call Stack” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.