Recursividad

Hasta ahora, una función llamaba a otra. La recursividad consiste en que una función se llame a sí misma. Suena a truco o a error, y es una técnica perfectamente normal: sirve para resolver problemas que se pueden definir en términos de una versión más pequeña de sí mismos.

La imagen clásica es la de las muñecas rusas: para vaciar una muñeca hay que abrirla y vaciar la de dentro, que es el mismo problema con una muñeca más pequeña, y así hasta llegar a la última, que ya no tiene nada dentro. Esa última es la que hace que el proceso termine.

La idea encaja de forma natural con muchas definiciones matemáticas. El factorial de un número es ese número multiplicado por el factorial del anterior. La suma de los n primeros números es n más la suma de los n menos uno primeros. En ambos casos, la definición se apoya en sí misma aplicada a un caso más pequeño, y eso es exactamente lo que una función recursiva expresa en código.

Fuera de las matemáticas también aparece: recorrer las carpetas de un disco duro es recursivo, porque dentro de una carpeta puede haber otras carpetas que se recorren igual, y recorrer las respuestas encadenadas de un foro también.

Un problema es candidato a resolverse de forma recursiva cuando se puede describir en función de una versión más pequeña de sí mismo, y existe un caso mínimo cuya solución se conoce directamente.

Toda función recursiva bien escrita tiene exactamente dos partes, y ninguna de las dos es opcional.

• El caso base es la situación más sencilla, aquella cuya solución se sabe sin necesidad de llamar a nada. Es la muñeca que ya no tiene nada dentro, y es lo único que puede detener el proceso.
• El caso recursivo es el que resuelve el problema llamando a la propia función con datos más pequeños, y es imprescindible que en cada llamada los datos se acerquen al caso base.

function void cuentaAtras(entero n) {
    if (n == 0) {                 // CASO BASE
        escribir("Empieza el examen")
        return
    }
    escribir(n)                   // CASO RECURSIVO
    cuentaAtras(n - 1)            // se llama a si misma con un dato menor
}

cuentaAtras(3)

// Escribe:  3  2  1  Empieza el examen

• La llamada inicial es cuentaAtras(3). Como 3 no es 0, se escribe el 3 y se llama a cuentaAtras(2).
• Esa llamada escribe el 2 y llama a cuentaAtras(1). Y esa escribe el 1 y llama a cuentaAtras(0).
• Ahora sí se cumple el caso base: se escribe el aviso, el return termina esa llamada y no se genera ninguna llamada nueva.
• A partir de ahí, cada llamada pendiente termina y devuelve el control a la que la había hecho, deshaciendo el camino hasta la primera.

Los dos errores que hay que vigilar son igual de graves. El primero es olvidar el caso base: sin él nada detiene la cadena de llamadas. El segundo es más sutil: tener caso base pero no acercarse a él, por ejemplo llamando a cuentaAtras(n) en vez de cuentaAtras(n - 1). El caso base está escrito, pero nunca se alcanza.

El caso base es lo que hace que la recursión termine. Sin él, o sin que cada llamada se acerque a él, la función se llama sin fin y el programa acaba cayendo por desbordamiento de la pila.

El factorial de un número entero positivo es el producto de todos los enteros desde uno hasta ese número. El factorial de 4 es 4 por 3 por 2 por 1, es decir, 24. Y por convenio, el factorial de 0 vale 1.

Lo que lo convierte en el ejemplo de manual de la recursividad es que se puede definir de otra manera equivalente: el factorial de n es n multiplicado por el factorial de n menos uno. Esa segunda definición se traduce a código casi palabra por palabra.

function entero factorial(entero n) {
    if (n <= 1) {
        return 1              // CASO BASE
    }
    return n * factorial(n - 1)   // CASO RECURSIVO
}

La función completa son cinco líneas. La condición del if recoge el caso base: el factorial de 1 y el de 0 valen 1 y se devuelven directamente. La última línea es la definición matemática literal: n multiplicado por el factorial del anterior. Lo importante es entender que, al llegar a esa línea, la multiplicación no se puede hacer todavía: primero hay que esperar a que la llamada interna devuelva su resultado.

factorial(4)
  = 4 * factorial(3)          <- queda a la espera
        = 3 * factorial(2)      <- queda a la espera
              = 2 * factorial(1)<- queda a la espera
                    = 1          <- CASO BASE: ya devuelve

Ahora se deshace el camino, resolviendo lo que estaba a la espera:

              2 * 1  = 2
        3 * 2        = 6
  4 * 6              = 24

factorial(4) = 24

El esquema muestra las dos fases que tiene toda recursión y que conviene distinguir. En la fase de descenso se van generando llamadas cada vez más pequeñas y ninguna termina: todas quedan a medias, esperando. En la fase de ascenso, a partir del caso base, cada llamada recibe el resultado de la que había lanzado, completa su multiplicación y devuelve el suyo. El resultado final se construye de dentro hacia fuera.

Mientras se desciende no se calcula nada: solo se acumulan llamadas pendientes. Todos los cálculos ocurren al volver, después de tocar el caso base.

Cualquier problema que se pueda resolver de forma recursiva se puede resolver también con un bucle, y al revés. Son dos caminos para lo mismo, así que la elección se decide por claridad y por coste.

// El mismo factorial, con un bucle
function entero factorialIterativo(entero n) {
    entero resultado = 1
    for (entero i = 2; i <= n; i++) {
        resultado = resultado * i
    }
    return resultado
}

La versión iterativa parte de un acumulador a 1 y lo va multiplicando por 2, 3 y así hasta n. Hace exactamente el mismo cálculo que la recursiva, pero sin generar ninguna llamada extra: todo ocurre dentro de una sola ejecución de la función, con lo que la memoria que consume no depende del tamaño de n.

La regla práctica es sencilla: cuando el problema es recursivo por su propia definición (recorrer un árbol, explorar carpetas dentro de carpetas), la versión recursiva es mucho más corta y más fácil de leer. Cuando se trata de recorrer algo de principio a fin o de acumular un total, el bucle es más directo y más barato.

Recursividad e iteración son equivalentes en capacidad. La recursiva gana en claridad cuando el problema lo es por naturaleza; la iterativa gana siempre en consumo de memoria.

Cada vez que un programa llama a una función, el sistema tiene que apuntar dónde estaba para poder volver, y además reservar sitio para los parámetros y las variables locales de esa llamada. Todo eso se guarda en una zona de memoria llamada pila, que funciona apilando: la última llamada realizada es la primera en retirarse.

En una función recursiva, mientras se desciende ninguna llamada ha terminado todavía, así que todas siguen ocupando su sitio en la pila a la vez. Con factorial(4) hay cuatro llamadas apiladas; con factorial(50.000) habría cincuenta mil. Y la pila tiene un tamaño limitado.

Cuando esa pila se llena, el programa se detiene con el error conocido como desbordamiento de pila o stack overflow. Ocurre por dos motivos distintos que conviene no confundir: porque la recursión sea infinita, y entonces es un error de programación, o porque la profundidad legítima sea demasiado grande, y entonces el algoritmo es correcto pero no sirve para ese tamaño de datos.

// 1. Sin caso base: no para nunca
function entero mal(entero n) {
    return n * mal(n - 1)
}

// 2. Con caso base, pero sin acercarse a el
function entero peor(entero n) {
    if (n <= 1) { return 1 }
    return n * peor(n)        // el argumento no disminuye
}

// 3. Correcta, pero con una profundidad enorme
factorial(1000000)            // el algoritmo es valido; la pila, no

Los dos primeros casos son errores claros: en el primero falta el caso base y en el segundo está escrito pero es inalcanzable, porque el argumento nunca disminuye. El tercero es el más instructivo, porque la función es correcta y aun así el programa cae: la recursividad tiene un techo de profundidad que la iteración no tiene.

La pila se llena porque las llamadas pendientes se acumulan sin cerrarse. Por eso el desbordamiento es el riesgo característico de la recursividad, igual que el bucle infinito lo es de la iteración.

Lo que la pila guarda por cada llamada es un bloque llamado registro de activación o marco de pila. Contiene la dirección de retorno (el punto exacto al que hay que volver), los argumentos recibidos, las variables locales de esa llamada y el espacio donde se dejará el valor devuelto.

Esos marcos son la razón de que cada llamada recursiva tenga sus propias variables, independientes de las de las demás llamadas de la misma función. Cuando en factorial(4) hay cuatro llamadas vivas, hay cuatro parámetros llamados n valiendo 4, 3, 2 y 1 al mismo tiempo, cada uno en su marco.

Estado de la pila justo al alcanzar el caso base de factorial(4):

      +---------------------------+  <- cima
      | factorial(1)   n = 1      |
      +---------------------------+
      | factorial(2)   n = 2      |
      +---------------------------+
      | factorial(3)   n = 3      |
      +---------------------------+
      | factorial(4)   n = 4      |
      +---------------------------+  <- base

Se retiran en orden inverso al que entraron: primero la de arriba.

Se llama recursión de cola a aquella en la que la llamada recursiva es lo último que hace la función, sin ninguna operación pendiente después. El factorial del ejemplo NO es de cola, porque al volver todavía queda una multiplicación por hacer. Cuando sí lo es, algunos compiladores aplican una optimización que reutiliza el mismo marco de pila en vez de apilar uno nuevo, con lo que la recursión pasa a consumir memoria constante y deja de poder desbordar.

Un último caso a distinguir es la recursión múltiple, en la que una llamada genera más de una llamada recursiva. La sucesión de Fibonacci escrita de forma directa es el ejemplo típico: cada llamada lanza dos, esas cuatro y así sucesivamente, con lo que el número total de llamadas crece de forma exponencial y se repiten cálculos idénticos una y otra vez. La versión iterativa del mismo problema es lineal.

La recursión de cola es la que no deja ninguna operación pendiente tras la llamada, y es la única que se puede optimizar para no consumir pila. El factorial escrito de la forma habitual no cumple esa condición.