Recursión y la pila de llamadas

De qué trata este capítulo

La recursión es una función que resuelve un problema llamándose a sí misma sobre una versión más pequeña del mismo problema. No es una estructura de datos — es una técnica — pero corre sobre una que ya construiste: la pila de llamadas del capítulo de stacks. Cada llamada mete un frame; cada retorno saca uno. Así que la recursión en realidad es un stack que no tienes que administrar a mano, y entender eso es la diferencia entre que la recursión se sienta como magia o se sienta como maquinaria. Este capítulo lo aterriza con las Torres de Hanói, cuya solución recursiva son tres líneas y cuyo costo es exponencial, y deja preparado el terreno para los sorts de divide y vencerás que llenan el resto del tier.

Un poco de historia

Las Torres de Hanói las inventó en 1883 el matemático francés Édouard Lucas, que las vendió como juguete envuelto en una leyenda: en un templo, unos monjes mueven 64 discos de oro entre tres postes, y cuando terminen, se acaba el mundo. Estamos a salvo por un buen rato — ya veremos por qué. La recursión como idea de programación es casi tan vieja como la programación misma: John McCarthy la metió en LISP en 1958, convirtiendo el que una función se llame a sí misma en algo de primera clase en lugar de un truco, y la teoría matemática de las funciones recursivas (Kleene, Church y otros en los años treinta) es anterior a las computadoras que la ejecutan. La pila de llamadas que hace que la recursión funcione en hardware — un frame por llamada — se estandarizó en esa misma época de los cincuenta que nos dio el stack. Así que el rompecabezas, la técnica y la maquinaria se juntan justo aquí.

La intuición

Una solución recursiva tiene dos partes, y las dos son obligatorias. El caso base es la versión más chica del problema que puedes contestar de inmediato — el punto donde la recursión se detiene. El caso recursivo resuelve un problema más grande reduciéndolo a uno o más problemas más chicos del mismo tipo y combinando sus respuestas. Si falta cualquiera de los dos — sin caso base, o con un caso recursivo que no achica el problema — la recursión nunca para y truena.

Las Torres de Hanói son la ilustración perfecta porque la idea recursiva es toda la solución. Para mover n discos del poste A al poste C: quitas de en medio los n−1 discos de arriba pasándolos al poste B (un problema de Hanói más chico), mueves el disco más grande de A a C, y luego mueves esos n−1 discos de B a C (otro problema de Hanói más chico). Nunca dices cómo mover n−1 discos — confías en que la recursión lo haga, igual que estás confiando en ella para mover n. Ese acto de fe, "asume que funciona para lo más chico y úsalo para resolver lo más grande", es la manera de pensar recursivamente.

Complejidad: cómo escala

El costo de una recursión sale de su recurrencia — una fórmula del trabajo en tamaño n expresado en términos de tamaños más chicos. Hanói hace dos subproblemas de tamaño n−1 más un movimiento:

Eso es exponencial. Cuatro discos toman 15 movimientos, diez toman 1023, veinte toman más de un millón, y los 64 discos de oro de Lucas toman $2^{64}-1$ movimientos — como 585 mil millones de años a un movimiento por segundo, así que los monjes no son ninguna amenaza. La gráfica deja la forma clarísima — la cuenta de movimientos se duplica con cada disco que agregas:

El espacio es un costo aparte, y es el que la recursión le suma a cualquier algoritmo: cada llamada pendiente mantiene un frame en la pila de llamadas, así que una recursión de profundidad d usa $O(d)$ de espacio de stack aunque una versión iterativa usara O(1). En Hanói la profundidad es apenas n, pero en una recursión que baja n niveles con una n grande, ese espacio de stack — y el límite que Python le pone — se vuelve la restricción.

En qué es buena y en qué no

La recursión es la herramienta correcta cuando un problema es autosimilar por naturaleza — cuando una instancia grande de verdad se descompone en instancias más chicas de la misma forma. Árboles, sorts de divide y vencerás, búsquedas con backtracking y cualquier cosa definida por una recurrencia salen más cortos y más claros como recursión que como loop administrado a mano, porque la pila de llamadas hace la contabilidad que si no tendrías que escribir tú. Cuando la estructura embona, el código recursivo muchas veces se lee como la definición del problema.

Donde te cuesta es en llamadas y profundidad. Cada llamada recursiva tiene overhead — un frame que entra y sale — que un loop se ahorra, y todos los lenguajes ponen un tope a qué tan profundo puede crecer el stack. Cuando una recursión tiene un gemelo iterativo trivial (factorial, sumar una lista), el loop casi siempre es la mejor opción. Y una recursión que puede irse muy profundo con entradas reales va a desbordar el stack; ahí o la reescribes como loop o haces el stack explícito, cambiando el stack del lenguaje por uno que tú controlas.

Los datos, o las entradas

La animación resuelve un Hanói de cuatro discos — 15 movimientos, lo bastante poco para verlos todos. El duelo calcula factoriales con n creciente para medir cuánto cuesta la recursión en sí contra su gemelo iterativo y contra math.factorial. Y la gráfica de crecimiento es pura aritmética: la cuenta exacta de movimientos $2^n - 1$, que no necesita ningún benchmark porque es exacta.

Constrúyela, una función a la vez

Aquí está el solucionador completo de Hanói — la recursión de tres líneas que se lee como la estrategia: mueve n−1 a un lado, mueve el disco grande, regresa los n−1:

def hanoi(n, source, target, auxiliary, moves=None):
    """Move n disks from `source` to `target` using `auxiliary`, one disk at a
    time, never placing a larger disk on a smaller one.

    The recursion IS the strategy: to move n disks, first move the top n-1 out of
    the way onto the spare peg, move the single largest disk across, then move the
    n-1 back on top of it. Each of those "move n-1" steps is the same problem, one
    size smaller — so the function calls itself twice."""
    if n == 0:
        return
    hanoi(n - 1, source, auxiliary, target, moves)   # n-1 disks off to the spare peg
    if moves is not None:
        moves.append((n, source, target))            # move the big disk across
    hanoi(n - 1, auxiliary, target, source, moves)   # n-1 disks back on top

El factorial es la recursión completa más chica que existe — un caso base y una llamada a sí misma:

def factorial(n):
    """The textbook recursion: n! = n * (n-1)!, bottoming out at 0! = 1. The base
    case is what stops the recursion — forget it and you recurse forever."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)

Y aquí está la transformación que le quita el misterio a la recursión: sumar una lista anidada con la pila de llamadas, y luego el mismo resultado con un stack explícito. La segunda es lo que la primera venía haciendo todo el tiempo — prueba de que la recursión es nada más un stack disfrazado, y tu salida de emergencia cuando el límite de profundidad se asoma:

def sum_nested(node):
    """Recursively sum a nested list (a tree of numbers). The call stack quietly
    remembers where you were in each level."""
    total = 0
    for child in node:
        total += sum_nested(child) if isinstance(child, list) else child
    return total


def sum_nested_iter(root):
    """The same sum with an EXPLICIT stack instead of recursion. This is exactly
    what the call stack was doing under the recursive version — made visible.
    Any recursion can be rewritten this way; sometimes you must, to dodge Python's
    recursion-depth limit."""
    stack = [root]
    total = 0
    while stack:
        node = stack.pop()
        if isinstance(node, list):
            stack.extend(node)
        else:
            total += node
    return total

Míralo funcionar

Aquí está el Hanói de cuatro discos resolviéndose solo, un movimiento por frame. Los cuatro discos empiezan apilados en el poste A, el más grande hasta abajo. Avanza paso a paso y observa el patrón que produce la recursión: para llevar el disco grande de abajo de A a C, todo lo que está encima primero tiene que migrar a B y luego regresar. Quince movimientos, y ni uno solo pone un disco más grande sobre uno más chico — la recursión lo garantiza. Fíjate en la autosimilitud: los primeros siete movimientos son un solve completo de tres discos que lleva los tres de arriba a B, y los últimos siete son otro que los regresa:

El código completo

Las dos versiones en un solo lugar — cambia entre ellas. La pestaña desde cero trae las recursiones: Hanói, factorial y la reescritura con stack explícito. La pestaña de librería es math.factorial, la versión iterativa en C que realmente llamarías — un recordatorio de que la librería estándar seguido desenrolla la recursión en un loop por exactamente las razones que da este capítulo.

"""Recursion — a function that solves a problem by calling itself on a smaller
piece of the same problem.

This isn't a data structure; it's a technique, and it runs on one you already
know. Every recursive call pushes a frame onto the call stack from chapter four;
returning pops it. So recursion is really just a stack you don't have to manage
by hand. This chapter makes that concrete with the Towers of Hanoi — a puzzle
whose recursive solution is three lines and whose cost is exponential.
"""


# region: hanoi
def hanoi(n, source, target, auxiliary, moves=None):
    """Move n disks from `source` to `target` using `auxiliary`, one disk at a
    time, never placing a larger disk on a smaller one.

    The recursion IS the strategy: to move n disks, first move the top n-1 out of
    the way onto the spare peg, move the single largest disk across, then move the
    n-1 back on top of it. Each of those "move n-1" steps is the same problem, one
    size smaller — so the function calls itself twice."""
    if n == 0:
        return
    hanoi(n - 1, source, auxiliary, target, moves)   # n-1 disks off to the spare peg
    if moves is not None:
        moves.append((n, source, target))            # move the big disk across
    hanoi(n - 1, auxiliary, target, source, moves)   # n-1 disks back on top
# endregion


# region: factorial
def factorial(n):
    """The textbook recursion: n! = n * (n-1)!, bottoming out at 0! = 1. The base
    case is what stops the recursion — forget it and you recurse forever."""
    if n <= 1:
        return 1
    return n * factorial(n - 1)
# endregion


# region: factorial_iter
def factorial_iter(n):
    """The same answer with a loop instead of recursion. Every recursion has an
    iterative twin; when the twin is this simple, prefer it — no call overhead,
    no depth limit."""
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result
# endregion


# region: explicit_stack
def sum_nested(node):
    """Recursively sum a nested list (a tree of numbers). The call stack quietly
    remembers where you were in each level."""
    total = 0
    for child in node:
        total += sum_nested(child) if isinstance(child, list) else child
    return total


def sum_nested_iter(root):
    """The same sum with an EXPLICIT stack instead of recursion. This is exactly
    what the call stack was doing under the recursive version — made visible.
    Any recursion can be rewritten this way; sometimes you must, to dodge Python's
    recursion-depth limit."""
    stack = [root]
    total = 0
    while stack:
        node = stack.pop()
        if isinstance(node, list):
            stack.extend(node)
        else:
            total += node
    return total
# endregion

"""Recursion is a technique, not a data structure, so there's no single library to
race against. The honest counterpart is twofold: for problems with an iterative
twin, the loop version is the "reference" (and usually what the standard library
ships — `math.factorial` is iterative C, not recursive); and for the general case,
an explicit stack is the mechanical way to remove recursion.

So the face-off compares our recursive code against its iterative equivalent and
against `math.factorial`, to measure what the recursion itself costs.
"""
import math


# region: math_factorial
def factorial_lib(n):
    """math.factorial: the standard library's version — iterative, in C, and the
    one you'd actually call. No recursion, so no depth limit and no call overhead."""
    return math.factorial(n)
# endregion

Desde cero vs librería

Para un problema con gemelo iterativo, la recursión es un impuesto chico. Calculando el factorial en n = 800, nuestra versión recursiva tardó como 0.12 ms, el gemelo iterativo 0.08 ms (el overhead de llamadas de la recursión, más o menos 1.4 veces más lento), y math.factorial 0.01 ms — la implementación en C, un orden de magnitud más allá de las dos. La lección no es que la recursión sea lenta; es que cuando existe un loop limpio, gana tanto en velocidad como en el límite de profundidad, así que la recursión debería ganarse su lugar haciendo el código genuinamente más claro o embonando con un problema que ningún loop expresa bien. Hanói es ese tipo de problema — intenta escribir su solucionador como loop y vas a terminar simulando un stack, que es justo la recursión que estabas evitando.

Dónde te la vas a encontrar de verdad

La recursión es el lenguaje natural de cualquier cosa con forma de árbol, que es casi todo lo que queda de este libro. Cada recorrido de árbol es una recursión. Los sorts de divide y vencerás — merge sort y quicksort, que siguen — son recursiones que parten, resuelven y combinan. Las búsquedas con backtracking (N-Reinas, más adelante) recurren hacia abajo por una decisión y deshacen al regresar. Los parsers recurren por gramáticas anidadas; los recorridos de sistemas de archivos recurren por directorios; las búsquedas en grafos recurren (o usan el stack explícito que mostró este capítulo) por los vecinos. Donde sea que un problema contenga copias más chicas de sí mismo, la recursión es cómo lo escribes.

Puntos clave

La recursión resuelve un problema reduciéndolo a instancias más chicas de sí mismo, deteniéndose en un caso base, y corre sobre la pila de llamadas — cada llamada es un frame, así que la profundidad cuesta O(d) de espacio y está acotada por el lenguaje. Su costo es lo que diga su recurrencia, que en Hanói es un exponencial $2^n - 1$. Cuando existe un gemelo iterativo casi siempre es la mejor opción, pero para problemas genuinamente autosimilares la recursión es más corta, más clara y más cercana a la definición que cualquier loop.

La técnica empieza a valer la pena desde ahora. Los siguientes tres capítulos son sorts, y los mejores — merge sort y quicksort — son la recursión en su forma más útil: parte el array, ordena las mitades recurriendo, combina. Ten presente la imagen de Hanói: resuelve el problema más chico confiando en la recursión, y todo lo demás se acomoda solo.