Llevo un par de meses bastante entretenido con el libro del MIT «Structure and Interpretation of Computer Programs». Si bien el MIT nos permite el acceso gratuitamente a todo su contenido aquí, es un libro genial que realmente vale la pena comprárselo.

En uno de sus primeros capítulos, donde se contrastan los procesos iterativos con los recursivos y como aquel que no quiere la cosa, en un ejercicio aparentemente inocente aparece un procedimiento que computa una variante de la función matemática de Ackermann:

(define (A x y)
    (cond ((= y 0) 0)
    ((= x 0) (* 2 y))
    ((= y 1) 2)
    (else (A (- x 1)
        (A x (- y 1))))))

Dicha función es famosa en teoría de la computación. Lo que sorprende de dicha función, a diferencia de las que habitualmente se usan como función «modelo» para enseñar qué es la recursividad, es que no es recursiva primitiva. El ejemplo típico de la función recursiva es la que nos da el factorial de un número n:

(define (factorial n)
    (if (= n 1)
    1
    (* n (factorial (- n 1)))))

El proceso que seguiría para calcular por ejemplo el factorial de 6 sería:

factorial(6)

6 * factorial(5)

6 * (5 * factorial(4))

6 * (5 * (4 * factorial(3)))

6 * (5 * (4 * (3 * factorial(2))))

6 * (5 * (4 * (3 * (2 * factorial(1)))))

Este es el punto en que más se carga la pila, a partir de aquí serían «pops»:

6 * (5 * (4 * (3 * (2 * 1))))

6 * (5 * (4 * (3 * 2)))

6 * (5 * (4 * 6))

6 * (5 * (24))

6 * (120)

720

Las funciones recursivas «típicas» siguen éste patrón, se van sumergiendo hasta llegar a un punto de inflexión a partir del cual van emergiendo hasta aflorar el resultado final. La función de Ackermann podría parecer que transcurre igual, por ejemplo (A 1 6) sería:

(A 1 6)

(A 0 (A 1 5))

(A 0 (A 0 (A 1 4)))

(A 0 (A 0 (A 0 (A 1 3))))

(A 0 (A 0 (A 0 (A 0 (A 1 2)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))

(A 0 (A 0 (A 0 (A 0 (A 0 2)))))

(A 0 (A 0 (A 0 (A 0 4))))

(A 0 (A 0 (A 0 8)))

(A 0 (A 0 16))

(A 0  32)

64

Es decir, 2⁶ De hecho, para todo (A 1 n) el resultado siempre será 2ⁿ Pero veamos por ejemplo como transcurre al calcular (A 2 4):

(A 2 4)

(A 1 (A 2 3))

(A 1 (A 1 (A 2 2)))

(A 1 (A 1 (A 1 (A 2 1))))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

…

Como se puede observar, se va profundizando para después emerger y a continuación volver a sumergirse. Después de un largo proceso recursivo, el resultado final que acaba dando es 65536, es decir, 2¹⁶.