An execution context stack, commonly called a call stack, keeps active function calls in order. Picture a pile of barbecue to-do notes: push a new task on top, then pop it when finished. section 3.3 section 3.4
When one function calls another, the caller pauses in a partially completed state. Its variables remain stored while the new call is pushed above it. Returning pops the newer call, so execution resumes where the caller stopped. section 3.4
Recursion makes the stack especially visible:
- Each recursive call receives its own function variables and occupies another stack entry. section 3.5
- The stack stores the unfinished work that a recursive algorithm would otherwise track in a separate pile. section 3.5
- A recursion that never reaches its base case keeps adding calls, making the stack grow very large and consume memory. section 3.6
Quicksort and stack height
Quicksort with a poor pivot can create a long call stack of O(n) entries; repeatedly dividing the array in half creates a shorter O(log n) stack. The stack height helps explain why the corresponding best-case running time is O(n log n), while the worst case is O(n²). section 4.5
def greet(name):
print("hello, " + name + "!")
greet2(name)
print("getting ready to say bye...")
bye()
Follow the nested greet, greet2, and bye calls while matching each call to its stack entry. section 3.4
