Entendiendo la recursividad

Por María Guerra Suárez

Para mí, la recursividad era algo bastante difícil de entender. Esto me llevaba pasando desde la universidad. No sé si es por la forma en la que se explica normalmente, o es que soy yo la que no terminaba de verlo. Sabía que era una herramienta muy potente, pero para mí, era más simple comprender y utilizar la forma iterativa. Y es así como me olvidé por completo de la recursividad durante muchos años.

Realizando el curso Testing y TDD, volví a toparme con este concepto. Y es que me resultaba complicado realizar por mí misma algunas katas propuestas. A ver, sí que las realizaba, pero usando bucles for. Sin embargo, quería poder aplicar con más facilidad, el paso 8 de la premisa de la prioridad de transformación, propuesta por Robert C. Martin, sin morir en el intento. Es por ello, que me aventuré a buscar en Internet cómo funciona la recursividad orientada a la programación, (ya que la mayoría de información con la que me topaba, mostraban ejemplos matemáticos que hacían que me explotase el cerebro aún más). Da la casualidad que encontré un post que hablaba de la funcionalidad de la recursividad, explicando el proceso que se lleva a cabo en la memoria del ordenador. Y fue ahí cuando se me encendió la bombilla.

No sé si a alguien más le ha podido pasar lo mismo que a mí. Por eso, voy a explicar la recursividad como a mí me habría gustado que me la explicaran en su momento.

Pondré como ejemplo el que todos ponen: la función factorial. Pero en este caso, sin fórmulas matemáticas. En vez de eso, usaré dibujitos de una pila.

1
2
3
4
5

function factorial(number: number) {
  if (number < 0) throw new Error("The number must be positive");
  if (number === 0) return 1;
  return number * factorial(number - 1);
}

Partiendo de como funciona la memoria de un ordenador, podemos dibujar una pila de tipo LIFO (Last In First Out), para almacenar las peticiones que se generan cuando queremos resolver factorial(3).

Sabemos que, la primera petición (en este caso factorial(3)) se almacenará en lo más bajo de la pila. Encima se irán insertando el resto de las llamadas, hasta llegar al caso base, el cual quedará al principio del todo.

Como ya la función nos devuelve un valor para ese caso, se libera esa llamada de la pila y se sustituye todas las demás llamadas a factorial(0) almacenadas por ese valor.

Esto nos deja resuelta la llamada a factorial(1), liberándose también de la pila y sustituyéndose por el resultado en otras llamadas almacenadas. Esta operación se repetirá hasta llegar al final de la pila, resolviendo la petición inicial y, por fin, devolviendo su resultado.

¿Por qué lo entendí mejor así? La verdad es que no lo sé. Supongo que ver cómo se iba resolviendo de arriba a abajo, hizo que lo interiorizara más. O quizás es que, al entender un poco más cómo el ordenador procesaba las peticiones, lo hizo más fácil.

Si eres una de esas personas con el mismo problema que yo, y este artículo te ha ayudado a entender un poco más el funcionamiento de la recursividad, te invito a que lo dejes en los comentarios. Si por el contrario, ya entendías la recursividad y sabes otra forma de explicarla, te animo a que la compartas.