🎓 A1Learner
🔍
0 of 100 lessons completed

DSA The Call Stack

The call stack is the pile of frames that holds unfinished function calls. A frame is the stored details of one call, like its local values.

Calls finish in reverse order

A call must finish before the call below it can continue. The prints show the calls ending in reverse order to their starts.

def third():
    print("third runs")

def second():
    print("second starts")
    third()
    print("second ends")

def first():
    print("first starts")
    second()
    print("first ends")

first()

Counting the live depth

Depth is how many frames are live at one moment. Four extra calls push the depth from one up to five here.

def climb(steps, depth=1):
    if steps == 0:
        return depth
    return climb(steps - 1, depth + 1)

print("deepest depth:", climb(4))

A guarded endless call

Python stops endless recursion by raising an error called RecursionError. A try block can catch that error and report it cleanly.

def boom(n):
    return boom(n + 1)

try:
    boom(0)
except RecursionError:
    print("stopped by RecursionError")

Example

import sys

def show(n, depth=1):
    print("call", n, "at depth", depth)
    if n > 1:
        show(n - 1, depth + 1)

def dive(depth):
    if depth == 1 or depth % 250 == 0:
        print("live depth:", depth)
    dive(depth + 1)

print("recursion limit:", sys.getrecursionlimit())
show(3)
try:
    dive(1)
except RecursionError:
    print("RecursionError caught")
    print("Python stopped the calls to protect the stack")

Key points

  • Each active call adds one frame to the call stack.
  • Frames leave the stack in reverse order to their arrival.
  • Depth is memory, because every live frame stores its call details.
  • The default recursion limit in Python is 1000 frames.

In this example, the program first prints the recursion limit of 1000 frames. The show function then prints its live depth as its calls sink from one to three. The dive function calls itself with no base case, printing its depth at each milestone of 250. Python raises RecursionError before the stack runs out, and the try block catches it on purpose. The caught error is the guard working, not a bug in the program.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Three nested calls are active and none of them has finished yet. How many frames sit on the call stack?