Cómo funciona la recursión en algoritmos

Llamarse a sí mismo otra vez

Que un método se llame a sí mismo suena un poco raro, pero es más sencillo de lo que parece.
Para resolver «resolver(5)», basta con resolver «resolver(4)»; y para resolver «resolver(4)», basta con resolver «resolver(3)».
Es el mismo método, llamado otra vez con una entrada más pequeña.

La misma caja se llama a sí misma otra vez con una entrada más pequeña. (resolver(5) → resolver(4) → … → resolver(1))

Dentro de la caja hay una caja idéntica, y dentro de esa, otra idéntica, como espejos dentro de espejos.
Solo cambia una cosa: la entrada se achica en uno cada vez.
A fuerza de achicarse, al final se convierte en un problema diminuto que se resuelve al instante.

El suelo donde se detiene

¿Qué pasa si un método solo se llama a sí mismo sin parar? Baja sin fin.
Por eso la recursión siempre necesita un suelo que diga «detente aquí».
Un acuerdo como «cuando la entrada llegue a 1, no vuelvas a llamar; responde directamente».

Compara con suelo vs sin suelo. Con suelo se detiene en 1; sin suelo baja sin fin.

Con suelo, las llamadas bajan, se detienen justo ahí y desde ese punto suben llevando la respuesta.
Sin suelo, se hunden sin fin hacia 0 y los negativos, y nunca sale una respuesta.
Por eso, al usar recursión, hay que decidir primero el suelo.

Apilar y luego deshacer

La recursión arma su respuesta en dos pasos.
Al bajar, deja la respuesta para después y sigue llamándose a sí misma, apilando las llamadas.
Al tocar el suelo, sube en sentido contrario y va combinando una a una las cosas apiladas hasta completar la respuesta.

Apila al bajar y combina al revés desde el suelo. (mul(4) = 4x3x2x1 = 24)

Mientras baja, la respuesta todavía no se ve, y eso puede impacientar un poco.
Pero en cuanto toca el suelo, todo se deshace con facilidad en sentido contrario. Cuanto más se apiló, más hay que combinar al subir.
También conviene recordar que, si la pila crece demasiado, hasta una computadora sufre.

Una sola cosa con divide y vencerás

Recuerda la lección anterior. Partimos un problema grande por la mitad, resolvimos cada mitad y las juntamos.
Ese «partir y resolver cada parte» es, en realidad, recursión.
resolver(8) llama a resolver(4) y a resolver(4), y cada resolver(4) llama a su vez dos veces a resolver(2).

Partir como llamadas recursivas. (resolver(8) → resolver(4)·resolver(4) → resolver(2)×4)

Así que divide y vencerás y la recursión no son cosas aparte, sino una sola. Partir = llamarse a sí mismo otra vez.
Cuando un trozo es demasiado pequeño para partirlo, ese es el suelo, y las respuestas pequeñas que se juntan hacia arriba son el apilar y deshacer.
Todo lo que hemos visto se reúne aquí.

La recursión en una línea

La recursión se sostiene en tres pilares: se llama a sí misma con una entrada más pequeña, tiene un suelo donde se detiene y apila para luego deshacer en sentido contrario.
Con estos tres, hasta un problema que parece complicado se puede pasar con disimulo a «un yo más pequeño» y resolver.

Toca los tres pilares en orden para resumir. (se llama a sí misma → suelo donde se detiene → apilar y deshacer)

Pero hay algo con lo que tener cuidado. Al partir, a veces se acaba resolviendo el mismo problema pequeño una y otra vez.
Calcular la misma respuesta una y otra vez es perder el tiempo.
Hay un truco para anotar una respuesta una vez y volver a usarla, y esa es la próxima historia.