Base cases and progress

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

A base case returns without another recursive call. Every recursive branch must reduce a well-founded measure such as a nonnegative length. Both termination and meaning need proof.

Work through an example

fib(0)=0 and fib(1)=1. For n≥2, calls use n-1 and n-2, which approach the base cases. Negative inputs are rejected instead of recursing forever.

Time and space complexity

Naive Fibonacci has exponential time and O(n) maximum stack depth.

Why it works

Every call fulfills the same smaller-input contract.

Common mistakes

A base case alone does not ensure progress.
Handle values outside the contract explicitly.

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