Recursion

A recursive function solves a problem by calling itself on a smaller version of the same problem. Merge sort did exactly that. Every recursive function needs two parts: a base case small enough to answer directly, and a recursive case that moves towards it.

def factorial(n):
    if n == 1:              # base case
        return 1
    return n * factorial(n - 1)   # smaller problem

print(factorial(5))

factorial(5) is 5 × factorial(4), which is 4 × factorial(3), and so on down to factorial(1), which is just 1. Then the answers multiply back up: 1, 2, 6, 24, 120.

Each call waits for the one it made, and the computer keeps track of the waiting calls on the call stack (a stack, from the data structures course). Forget the base case, or never reach it, and the calls pile up until the stack runs out: Python stops with a RecursionError, its version of a stack overflow.

Recursion fits problems that are made of smaller copies of themselves: trees, folders inside folders, splitting a list in half. Anything recursive can also be written with a loop, and sometimes the loop is simpler.