Recursion

A recursive function is one that calls itself. It solves a problem by reducing it to a smaller version of the same problem until it reaches a case simple enough to answer directly.

The two ingredients

1. A base case that returns without recursing.
2. A recursive case that moves closer to the base case.

Without a base case the function calls itself forever and Python stops it with RecursionError.

Factorial

5 factorial is 5 × 4 × 3 × 2 × 1. Written recursively: n! = n × (n - 1)!, and 0! = 1.

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

print(factorial(5))

Trace it: factorial(3) returns 3 * factorial(2), which returns 2 * factorial(1), which returns 1 * factorial(0), which returns 1. The results multiply back up.

Sum of a list

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

print(total([1, 2, 3, 4]))

Fibonacci

Each number is the sum of the two before it.

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(i) for i in range(10)])

This version is elegant but slow, because it recomputes the same values many times. fib(30) makes over a million calls. Caching fixes it:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(80))

Walking nested data

Recursion shines with data that is itself nested, such as folders inside folders or lists inside lists.

def flatten(items):
    result = []
    for item in items:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4]], 5, [[6]]]))

Binary search

Find a value in a sorted list by repeatedly halving the search range.

def search(items, target, lo=0, hi=None):
    if hi is None:
        hi = len(items) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if items[mid] == target:
        return mid
    if items[mid] < target:
        return search(items, target, mid + 1, hi)
    return search(items, target, lo, mid - 1)

data = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
print(search(data, 23))
print(search(data, 7))

The recursion limit

Python limits the depth of recursion (about 1000 by default) to protect against runaway calls. Anything that might recurse thousands of times deep, like processing a long list one element at a time, should be a loop instead.

import sys
print(sys.getrecursionlimit())

Practice

1. Write a recursive power(base, exp) for non negative integer exponents.
2. Write count_down(n) that prints from n to 1 recursively.
3. Write sum_digits(n) that returns the sum of the digits of a positive integer using recursion.