Iterative conversion

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

Convert recursion by identifying what each frame remembers. Some recurrences compress to a few variables; traversals need an explicit stack of pending work and possibly a phase marker.

Work through an example

fib_iter keeps consecutive values (F(i),F(i+1)). Updating (a,b) simultaneously avoids overwriting a value needed for the other expression.

Time and space complexity

Iterative Fibonacci O(n) arithmetic steps/O(1) variables; integer sizes grow with n.

Why it works

Before iteration i, a=F(i), b=F(i+1).

Common mistakes

Sequential a=b; b=a+b uses the updated a incorrectly.
Explicit stacks still count as auxiliary space.

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