Funciones recursivas

Estudiaremos las funciones, con mucho más detalle, en el capítulo correspondiente. Aquí solo quiero hablarte de un concepto específico: funciones que vuelven a llamarse a sí mismas. Estas llamadas consecutivas resuelven los problemas de forma progresiva y se hacen cambiando alguno de los parámetros porque si no se cambia nada entre llamada y llamada caerás en una recursión infinita.

En el siguiente ejemplo, consideramos el caso de un jugador que está sufriendo una ráfaga de ataques consecutivos por parte de varios enemigos. Antes de pensar siquiera en la defensa del personaje, tenemos que saber cuánto daño acumulado sufriría por esa acción combinada.

La función dmg_accumulation recibe como parámetros:

• z_x - un slice que representa los ataques restantes por procesar,
• n_acc - un acumulador (un número que guarda la suma) del daño total que llevamos acumulando en cada llamada

En la primera llamada:

el slice z_x tiene todas las posiciones del array de ataques, y n_acc vale 0, que es el valor inicial, antes de hacer ninguna suma. Esto lo llamamos el “estado inicial”.

Para resolver un problema usando la recursividad  dividimos el problema en dos partes:

1. El caso base, y
2. El caso recursivo

El caso base es el problema más pequeño que sabemos resolver y que detiene la recursión. En nuestro caso, el problema más pequeño se da cuando ya no quedan más elementos en el slice z_x: no sumamos ya nada más y devolvemos el acumulador n_acc:

El caso recursivo, es cuando todavía hay elementos por procesar y dividimos el problema en subproblemas más pequeños. Sumamos el valor del primer elemento al acumulador y devolvemos el resultado de la llamada a la función con resto de los elementos y el nuevo acumulador:

Esta manera de solucionar usando la recursividad, alguna gente la recuerda mejor como el famoso “divide y vencerás”.

Recursión de cola

        En el ejemplo recursive_damage.zig, cada vez que la función se llama a sí misma, los parámetros enviados, en realidad no son los mismos que ha recibido. Podemos visualizar el slice como formado por dos partes: “la cabeza” (el primer elemento) y  “la cola” (el resto).

• El primer parámetro es un slice z_x pero sin “la cabeza” : z_x[1..] - esto es “la cola”,
• El segundo parámetro es el valor actual de n_acc sumando con la primera posición del z_x: n_acc + z_x[0]

Si ya no quedan más valores en el z_x la función termina devolviendo el acumulador:

        Este patrón, llamado Recursión de Cola (Tail Recursion), es muy común en la programación funcional.

Como ves, en vez de mantener una variable mutando dentro del bucle, como veremos en seguida con los bucles for y while, aquí pasamos el estado (el acumulador n_acc) en cada llamada. Fíjate que tanto z_x como n_acc son constantes. En cada llamada estamos creando un nuevo estado que no es mutable, y finalmente devolvemos el resultado acumulado como salida de la función.

Recursión no de cola

Como acabamos de ver, en la “Recursión de Cola”, primero sumamos “la cabeza” al acumulador y pasamos “la cola” y el acumulador actualizado a la siguiente llamada.

En una “recursión no de cola”, en el caso base - cuando ya no hay más elementos para procesar - devolvemos un 0 (no el acumulador) y  en el caso recursivo: devolvemos “la cabeza” sumada a la llamada recursiva con la cola.

En este caso, la llamada recursiva no es lo último que se hace. En cada llamada, la función tiene que esperar a que termine la siguiente llamada para poder hacer la suma con su valor. Este tipo de recursión no es optimizable - necesita mantener una pila (stack) de llamadas. Para visualizar como funciona, aquí un ejemplo:

Por esta razón, si te encuentras un caso parecido y decides resolverlo con funciones recursivas,  intenta usar siempre la recursión de cola: es más eficiente e incluso más fácil de transformar en un bucle si lo necesitas.

Función recursiva infinita

Una función recursiva hace una copia de sí misma en la memoria cada vez que se ejecuta una llamada. Si estas llamadas son demasiadas, o peor aún no hay una condición que pare el bucle, acabamos desbordando el espacio de memoria que el sistema operativo ha reservado para nuestro programa, como en el siguiente ejemplo:

Como puedes ver, si no hay una condición que pare la recursión, la función infinite_loop se llama a sí misma una y otra vez, sin límite. Como cada llamada ocupa un pequeño espacio en la pila de ejecución (se llama stack), al cabo de miles de llamadas ese espacio se agota y el sistema operativo mata el proceso, mostrando un mensaje de Segmentation fault (Fallo de segmentación). Este tipo de error suele pasar cuando el programa al final intenta acceder a una zona de la memoria que no le corresponde.

Recuerda como hemos provocado este error, porque vamos a ver algo interesante en seguida.

Antes, te animo por si quieres practicar, a añadir una condición de salida a la función infinite_loop del código recursive_infinite.zig.