Recursión normal y recursión con cola en Racket

Dani Rodríguez • 10 May 2014 • Permalink

Aprovechando que salvo algún trabajo que debo tener hecho para la semana que viene he terminado este curso en la universidad y ya puedo vivir más tranquilo, me ha dado por experimentar con uno de los lenguajes de programación que he aprendido este año y que es sin duda el que más me ha atraído: Scheme, o concretamente el dialecto que hemos estado usando en clase, Racket.

Se dice que Lisp/Scheme son lenguajes de programación de uso principalmente académico, y probablemente sea cierto, pero la forma en la que está hecho Racket, con su gran librería estándar llena de funciones y sus módulos de distinto tipo, incluyendo GUI, redes, servidores web y expresiones regulares hacen que este lenguaje sea conocido fuera de lo estrictamente académico. Por lo que veo en Wikipedia, Racket es el lenguaje de programación bajo el que opera el servidor del sitio web Hacker News y es un lenguaje de script que han usado algunos juegos de Naughty Dog.

En cualquier caso, ando este fin de semana intentando construir una implementación del autómata celular Langton’s Ant (la Hormiga de Langton). En esencia, la hormiga de Langton consiste en un tablero bidimensional de celdas que pueden ser blancas o negras. Una hormiga va moviéndose por el tablero y en función de una serie de reglas va cambiando el color de las celdas entre blanco y negro.

Y uno de los lenguajes de programación que estoy intentando usar para llevar a cabo esto es Racket, simplemente por pura curiosidad. La idea es hacer una interfaz gráfica donde se vea representado el tablero de colores y donde pueda ver a la hormiga y la dirección que lleva.

Un boceto de lo que quiero obtener. La hormiga se representa como una flecha en la parte derecha del tablero.

La pregunta es, ¿cómo implementar esto? De forma iterativa es fácil ver que se trata de hacer más o menos lo siguiente:

mientras condicion
    evaluar reglas
    mover hormiga
    cambiar color celda
fmientras

¿Qué es condicion? Veamos. Está determinado que la hormiga de Langton tiene tres modos de conducta, y llegado un momento pasa de un estado a otro. De acuerdo con la información que hay en Wikipedia, no se ha podido demostrar matemáticamente que este cambio de estado sea verdadero siempre, pero en todas las combinaciones probadas hasta el momento ha ocurrido que la hormiga pase entre tres estados:

1. Simple, moviéndose bien y creando hasta estructuras agradables con los colores.
2. Caos, donde empieza a moverse de forma irregular y aleatoria.
3. Emergente, de forma espontánea comienza a avanzar en línea recta hasta salirse de los límites del tablero, dejando tras de sí una estela recta de grosor variable. Por esa estela este modo también es apodado “modo autopista” ya que a veces la estela es bastante gruesa.

Por lo tanto, si la hormiga tarde o temprano abandonará el tablero, puedo hacer que se itere hasta que la hormiga abandone el tablero. Esa será mi condición. Cuando la hormiga se salga de los límites del tablero ya no tiene sentido que continúe evaluando.

El problema es que Racket es un lenguaje funcional, y preferiría poder expresar mi programa de una manera que no requiera recordar constantemente el estado. Algo que se puede hacer usando recursión. No tengo interés en programar de forma imperativa con Racket ya que para ello hubiese usado desde el principio C o Java, por lo que debo implementar cada paso como una llamada recursiva.

He visto simulaciones en YouTube y la hormiga puede dar millones de pasos hasta que abandona el tablero por lo que necesito una función recursiva que soporte ser recurrida miles y miles de veces sin reventar la pila del ordenador que estamos usando. Dada la cantidad de veces que puede iterarse, voy a considerar que lo que tengo es un bucle (casi) infinito por simplificar.

Es por ello que me puse a buscar en Internet cómo se puede implementar un bucle infinito en Scheme. Y el resultado es, que hay dos tipos de recursión: recursión normal y recursión de cola.

Recursión normal

La recursión normal es aquella en la que una función se invoca a sí misma, con la esperanza de obtener un resultado que luego pueda usarse dentro de la misma función para algo. Es decir, la llamada recursiva está en mitad del cuerpo de la recursión. Por ejemplo, en la función factorial se obtiene el factorial de otro número y luego ese valor se usa para otro cálculo, en este caso una multiplicación.

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

Por dentro, este tipo de recursión trabaja creando nuevos marcos de pila (stack frames) cada vez que se entra en un nuevo ciclo de la recursión; el resultado es que cada llamada sube en la pila. Esto es así hasta que llegamos al caso base, donde se obtiene un valor. A partir de aquí, volvemos a bajar en la pila, entregándole un valor al siguiente frame, y repitiendo esto hasta el final. De este modo, es posible usar esta función en la práctica.

> (factorial 12)
  479001600

El problema con la recursión normal está en que, si hay demasiados marcos de pila y se agota la pila, se produce un desbordamiento. No es posible crear más marcos de pila y por lo tanto no se puede continuar en la ejecución. Esto es lo que se conoce como stack overflow. Ocurre cuando, por ejemplo, quitamos el caso base en la función factorial. Se crean nuevos marcos, y más marcos, más marcos, más marcos hasta que la memoria dice ¡basta! y revienta. En DrRacket lanza un mensaje de error preguntando si queremos darle más memoria al programa.

(define (fact-inf n)
  (* n (fact-inf (sub1 n))))

> (fact-inf 12)
; Interactions disabled

Recursión de cola

En este caso, la llamada recursiva es lo último que hace la función antes de terminar. No hay ningún tipo de operación que se haga después de la llamada recursiva. Sirva como ejemplo la definición de la función máximo común divisor.

(define (mcd x y)
  (if (= y 0) x
      (mcd y (remainder x y))))

> (mcd 4093 11060)
  1

Y efectivamente, lo que hacen es que en vez de crear un nuevo marco de pila encima del viejo, simplemente reemplazan un marco por otro. De este modo, entre una llamada y la siguiente nunca se asciende en la pila, y por lo tanto, nunca se llega a saturar por culpa de la recursión.

El compilador de Racket optimiza la recursión de cola. De este modo, si quitase el caso base en mi función mcd, hiciese algún apaño al código para que no intente calcular y % 0, e intentase ejecutar este bucle infinito:

(define (mcd-inf x y)
  (mcd-inf y (remainder x (if (= y 0) 1 y))))

> (mcd-inf 4096 11000)

Lo que ocurriría es que esta función estaría llamándose a sí misma todo el rato, consumiendo CPU, claro está, pero sin consumir memoria. Mientras escribo esto la función sigue evaluándose en la ventana de DrRacket pero todavía no devuelve nada, y ya puede acabarse el mundo dentro de tropecientos mil millones de años que por entonces todavía estará mi ordenador ejecutando esta función sin descanso.

De hecho, puedo saber que no consume memoria porque en la parte de abajo de la ventana, no aparece el símbolo de reciclaje que indica que el recolector de basura está intentando hacer cosas, cosa que sí ocurre cuando lanzo la función fact-inf hasta que revienta.

Cuando la función no está optimizada, el recolector de basura entra con fuerza.

Conclusión

Si quiero que mi hormiga pueda avanzar de forma infinita sin que la memoria RAM de mi ordenador pida clemencia y sobre todo sin que el sistema operativo o DrRacket detenga la ejecución del programa, debo usar recursión de cola. De este modo, puedo repetir mi función miles de veces sin que la memoria se resienta.