Una función que se llama a sí misma: la recursión

Una función que se llama a sí misma

En la lección 9, una función agrupaba trabajo y recibía un nombre.
Dentro de ella, podías llamar a otras funciones.
La recursión va un paso más allá:
la función se llama a sí misma otra vez.
Como un espejo dentro de un espejo, lo mismo aparece una capa más adentro.

Tócalo. Cada toque añade un marco idéntico más adentro.

Es ingenioso, pero también un poco aterrador.
Si sigue llamándose así,
¿no seguirá para siempre?
Exacto. Por eso la recursión necesita una cosa esencial.

Necesita un punto para parar

Dos espejos sí siguen para siempre,
pero un computador no puede hacer 'para siempre'.
Por eso fijamos una regla:
'cuando el trozo sea bastante pequeño, para ahí.'
Sin esta regla de parada, gira sin fin y se cae.

Activa la regla de parada y se detiene en 3, 2, 1. Apágala y cae sin fin hasta romperse.

Piensa en este punto de parada como 'el suelo'.
Hasta llegar al suelo, sigue llamándose;
al tocar el suelo, deja de llamarse.
Ahora la clave es cómo lo partimos.

Una versión más pequeña del mismo problema

Este es el verdadero truco de la recursión.
Ve un problema grande como 'un paso + el mismo problema, pero más chico'.
Toda la escalera = un escalón + el resto de la escalera.
El 'resto' es el mismo problema, solo un escalón más chico.
Se encoge y encoge hasta llegar a 0 escalones.

Quita un escalón cada vez. Lo que queda es siempre el 'mismo pero más chico' problema.

Un problema difícil de pronto se vuelve fácil.
No tienes que resolverlo todo de una vez.
Solo encárgate de 'un escalón' y devuelve el resto a la misma función.
Pero ¿cómo regresa el trabajo que entregaste?

Baja y luego vuelve

La recursión se mueve en dos direcciones.
Primero baja hasta el suelo (llamándose una y otra vez).
Al tocar el suelo, sube de vuelta,
y cada nivel añade su propia parte.
Igual que apilar platos y luego quitarlos desde arriba.

Avanza paso a paso. Baja al suelo para 1+2+3 y luego sube juntando 6.

Este 'bajar y subir' es el corazón de la recursión.
Al bajar, divide el problema;
al subir, combina las respuestas.
El trabajo apilado se deshace desde el suelo, uno por uno.

El hermano del bucle, y más allá

La recursión y el bucle (lección 7) son hermanos.
Ambos 'hacen lo mismo muchas veces', pero
el bucle los pone uno al lado del otro,
mientras la recursión se adentra capa por capa.
Para carpetas dentro de carpetas, o ramas que se abren en ramas, la recursión encaja perfecto.

Cada toque divide otra rama. La misma regla dibuja un árbol entero por sí sola.

La función que agrupamos y nombramos (lección 9)
ahora puede incluso llamarse a sí misma.
Partir en chico, parar en el suelo, juntar de vuelta.
Esta sola idea abre carpetas, respuestas a respuestas, hasta resolver laberintos.
Luego iremos a emparejar y guardar muchos valores juntos.