Call stack and stack space

What is recursion?

Recursion happens when a function calls itself to solve a smaller version of a problem. A base case gives an answer without another call. Every call must move toward that base case. Calls also occupy memory until they return; this waiting memory is the call stack.

Example: To total [2, 3, 4], a recursive rule can add 2 to the total of [3, 4], then add 3 to the total of [4]. The total of an empty sequence is the base case: 0.

Helpful before this chapter

If these ideas are new, begin with:

Programming foundations Stacks

Understand the idea

Each call has its own local variables and return location. Suspended callers remain live while a child executes. Space follows the deepest active chain, not the total number of calls.

Work through an example

While fib(3) waits for fib(2), that call waits for fib(1). Only this path is simultaneously active; sibling calls happen later.

Time and space complexity

Depth d needs O(d) frame space; Python does not guarantee tail-call elimination.

Why it works

A frame resumes only after its called function returns.

Common mistakes

Do not assume recursion uses constant space.
Deep skewed inputs may exceed Python's recursion limit.

Chapter lab · Python implementation

A recursive function solves a smaller instance of the same contract. The lab computes Fibonacci with deliberately naive recursion to expose repeated subproblems, then uses fast exponentiation as a shrinking recurrence. A Python call stack is finite; large depths require an iterative design rather than assuming unlimited recursion.

This shared lab connects the chapter's topics. Follow the current lesson's worked example first, then trace the complete implementation. Additional algorithms described in topic exercises are variations you can implement independently.

def fib(n):
    if n<0:
        raise ValueError('nonnegative n required')
    if n<2:
        return n
    return fib(n-1)+fib(n-2)

def power(base,exponent):
    if exponent<0:
        raise ValueError('nonnegative exponent required')
    if exponent==0:
        return 1
    half=power(base,exponent//2)
    result=half*half
    return result*base if exponent%2 else result

def fib_iter(n):
    if n<0:
        raise ValueError('nonnegative n required')
    a,b=0,1
    for _ in range(n):
        a,b=b,a+b
    return a

Run and test the lab

Copy the implementation and these assertions into a Python 3 file and run it. An assertion failure means the actual result differs from the expectation. Add the current topic's exercise and boundary tests to deepen your understanding.

assert fib(6)==8 and fib(0)==0
assert all(fib(n)==fib_iter(n) for n in range(12))
assert power(3,5)==243 and power(9,0)==1
assert power(-2,3)==-8

CHECK YOUR UNDERSTANDING