Recursion versus iteration

The same algorithm both ways, the cost of a frame per call, repeated work, and stack overflow.

A2.3Recursion and computational thinkingA level20 min

Anything a recursive subroutine can do, a loop can also do, and the other way round. So why have both? This lesson compares them: how to turn one into the other, what each costs in time and memory, when recursion is the clearer choice, and what stack overflow really means.

The same algorithm, twice

Here is factorial written recursively and iteratively (with a loop):

def factorial_rec(n):
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)

def factorial_loop(n):
    result = 1
    for k in range(1, n + 1):
        result = result * k
    return result

for n in [0, 1, 5, 10]:
    print(n, factorial_rec(n), factorial_loop(n))

Run this in the simulator

Both give the same answers, but they use memory differently. The loop has one set of variables, whatever n is. The recursive version pushes a new stack frame for every call, so factorial_rec(10) has eleven frames on the stack at its deepest. Recursion depth n needs memory in proportion to n; the loop needs a fixed amount.

Turning recursion into a loop

For a subroutine that makes one recursive call, the conversion is usually direct:

1. the base case becomes the starting value, or the condition that ends the loop;
2. the general case becomes the body of the loop, which moves one step towards the base case each time round.

When a subroutine makes two or more recursive calls, as merge sort does, there is no simple loop. The iterative version has to keep its own stack of work still to do, doing by hand what the call stack did automatically.

The cost of repeated work

Recursion can hide a lot of work. The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, ..., each the sum of the two before. The recursive definition is short, but each call makes two more:

calls = 0

def fib_rec(n):
    global calls
    calls = calls + 1
    if n < 2:
        return n
    return fib_rec(n - 1) + fib_rec(n - 2)

def fib_loop(n):
    a, b = 0, 1
    for k in range(n):
        a, b = b, a + b
    return a

print("recursive:", fib_rec(20), "in", calls, "calls")
print("loop:     ", fib_loop(20), "in 20 times round the loop")

Run this in the simulator

fib_rec(20) makes 21,891 calls, because it works out the same smaller values again and again: fib_rec(18) is calculated in full twice, fib_rec(17) three times, and so on. The number of calls roughly multiplies by 1.6 each time n goes up by 1. The loop does 20 steps. Lesson A2.7 shows how a cache removes the repeated work while keeping the recursion.

Stack overflow

Every recursive call that has not yet returned holds a frame. If the recursion is too deep, the stack runs out of memory: a stack overflow. It happens when there is no base case, when the base case is never reached, or when the problem is simply too big for the stack.

import sys
print("Python's limit:", sys.getrecursionlimit(), "nested calls")

deepest = 0

def no_base_case(n):
    global deepest
    deepest = n
    return no_base_case(n + 1)

try:
    no_base_case(1)
except RecursionError:
    print("RecursionError after", deepest, "calls deep")

total = 0
for k in range(1, 3001):
    total = total + k
print("a loop 3000 times round is fine:", total)

Run this in the simulator

The call that failed would have needed a frame beyond the limit. A loop that runs 3,000 times is no problem at all, because it never adds a frame. The depth printed is less than the limit, because some frames are already in use by the program that runs your code.

Comparing the two

Some languages turn a call that is the very last action of a subroutine (a tail call) into a jump that reuses the current frame, which removes the memory cost. Python does not do this, so deep recursion in Python always uses the stack.

Recursion is the better choice when the problem is defined in terms of smaller copies of itself and the depth stays modest: searching a tree, sorting by splitting, or exploring a maze. Iteration is the better choice for straightforward repetition, or when the depth could be large.

Task: binary, both ways

Write two functions that each take a whole number n from 0 to 1,000 and return its binary digits as a string, with no leading zeros (0 gives "0", 6 gives "110"):

• to_binary_rec(n) must be recursive, with no loop;
• to_binary_loop(n) must use a loop.

Do not use bin or format. Then, for each n in [0, 1, 6, 37, 255], print one line <n>: <recursive answer> <loop answer>, for example 6: 110 110.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def to_binary_rec(n):
    return ""

def to_binary_loop(n):
    return ""

for n in [0, 1, 6, 37, 255]:
    print(f"{n}: {to_binary_rec(n)} {to_binary_loop(n)}")

Challenges

1. How many stack frames does to_binary_rec(255) use at its deepest? What about to_binary_rec(1000)?
2. Write sum_list(items) recursively: the sum of an empty list is 0, otherwise it is the first item plus the sum of the rest. Why is it a poor choice for a list of 5,000 readings?
3. Count the calls fib_rec(25) makes. Is the growth closer to doubling or to adding a fixed amount each time?