Returning versus accumulating state

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

Returning a value combines independent child results. Accumulating into shared state can avoid large returned objects but couples calls through mutation. Choose a clear contract and reset state between runs.

Work through an example

A subtree sum returns left_sum+node.value+right_sum. A path collector appends to a shared list but must undo an append after each branch.

Time and space complexity

Scalar returns use O(depth) stack; collecting output adds its output size.

Why it works

Returned results describe exactly their own subproblem; shared state must be restored for siblings.

Common mistakes

Shared mutable default lists leak across calls.
Returning inside a loop may skip later children.

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