Recursive decomposition

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

Recursive decomposition must cover the original problem without missing or duplicating required pieces. Specify how child results are combined, then apply the contract inductively.

Work through an example

power(3,5) computes power(3,2)=9 once, squares to 81, then multiplies by 3. Computing the same half twice would create unnecessary branching.

Time and space complexity

O(log exponent) multiplications/O(log exponent) stack, under bounded arithmetic.

Why it works

half equals base raised to floor(exponent/2); squaring and an optional factor reconstruct the exponent.

Common mistakes

Do not recurse on the same exponent.
Large integer multiplication costs are not constant in reality.

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