Recursion in practice

Introduction

The first recursion lesson showed the idea: a function that calls itself on a smaller problem, with a base case that stops it. This lesson solves three real problems that way. Watch the call stack in each: it is the clearest picture of how recursion works.

Thinking recursively means asking one question: if something else solved a slightly smaller problem for me, what would I still have to do? Once that clicks, many problems that look complicated become only a few lines long.

How it works

A fast power

def power(base, exp):
    if exp == 0:
        return 1
    half = power(base, exp // 2)
    if exp % 2 == 0:
        return half * half
    return half * half * base

print(power(2, 10))

Multiplying 2 by itself 10 times takes 10 steps. This version uses a trick: 2 ** 10 is (2 ** 5) ** 2, so it only needs half the exponent each time. The stack grows to five frames of power (exp 10, 5, 2, 1, 0) instead of ten. This halving idea, like binary search, gives O(log n) work.

The Tower of Hanoi

def hanoi(n, start, end, spare):
    if n == 0:
        return
    hanoi(n - 1, start, spare, end)
    print("Move disk", n, "from", start, "to", end)
    hanoi(n - 1, spare, end, start)

hanoi(2, "A", "C", "B")

Move a stack of disks from peg A to peg C, one disk at a time, never putting a larger disk on a smaller one. The recursive plan for n disks is short:

1. Move the top n - 1 disks out of the way, to the spare peg.
2. Move the largest disk to its target.
3. Move the n - 1 disks back on top of it.

With 2 disks that takes 3 moves; in general it takes 2 ** n - 1. Step through it and watch n, start, end and spare swap roles in each frame.

Syntax

def total(nums):
    if not nums:              # base case
        return 0
    return nums[0] + total(nums[1:])

Example

def total(nums):
    if not nums:
        return 0
    return nums[0] + total(nums[1:])

print(total([4, 7, 1]))

The total of a list is its first item plus the total of the rest. The base case is the empty list, whose total is 0. Step to the deepest point: the stack holds four frames of total, for [4, 7, 1], [7, 1], [1] and []. Then the answers flow back up: 0, then 1, then 8, then 12.

Line by line

1. total([4, 7, 1]) is not empty, so it needs 4 + total([7, 1]).
2. That needs 7 + total([1]), and then 1 + total([]).
3. total([]) meets the base case and returns 0.
4. The answers come back through the waiting calls: 1, then 8, then 12.

Expected result

12

In the real world

Folder trees, web page structures and sorting algorithms such as merge sort are naturally recursive. Compilers process programs recursively, too, because a program is built of expressions inside other expressions.

Common mistakes

• A base case that is never reached, such as calling total(nums) again instead of total(nums[1:]). The result is a RecursionError.
• Forgetting to return the recursive result: total(nums[1:]) on its own computes the answer and then throws it away.
• Recursing very deep. Python stops at about 1000 frames, so a loop is better for long lists.

Best practices

• Write the base case first.
• Make each call clearly smaller than the last.
• Use a loop for very long data, because of the depth limit.

Summary

Recursion breaks a problem into a smaller copy of itself and a base case that ends the calls. Fast power shows how halving makes recursion very efficient, and the Tower of Hanoi shows how a hard problem can have a short plan.

Practice

Write a recursive count_down(n) that prints n, n - 1, …, 1 and then Liftoff!. Then write a recursive reverse(text) that returns the text backwards.

Mark lesson complete