Soluciones que se llaman a sí mismas: recursión

Se llama a sí mismo otra vez

Que una solución se llame a sí misma
suena un poco raro.
Pero es simple.
Para hacer "resolver(5)"
solo haces "resolver(4),"
y para hacer "resolver(4)"
solo haces "resolver(3)."
La misma solución,
llamada otra vez con una entrada más chica.

La misma caja se llama con una entrada más chica. (resolver(5) → resolver(4) → … → resolver(1))

La misma caja dentro de una caja,
y la misma caja dentro de esa.
Como un espejo en un espejo.
Solo una cosa cambia,
la entrada se encoge paso a paso.
Encogiendo y encogiendo,
al final se vuelve un problema diminuto
que puedes resolver de inmediato.

Un suelo para parar

Si solo sigue llamándose,
¿qué pasa?
Baja para siempre.
Por eso la recursión debe tener
un suelo que diga
"para aquí."
"Cuando la entrada llegue a 1,
no llames más, solo responde,"
una promesa así.

Con suelo vs sin suelo. (Con: para en 1 · sin: baja para siempre)

Con un suelo,
baja, para justo ahí,
y sube de vuelta con una respuesta.
Sin un suelo,
baja para siempre hacia 0, negativos,
y nunca da una respuesta.
Así que al usar recursión,
fija el suelo primero.

Se apila y luego se deshace

Cómo arma una respuesta la recursión
lleva dos movimientos.
Al bajar,
deja la respuesta a un lado por ahora
y sigue llamándose, apilando.
Al tocar el suelo,
esta vez sube de vuelta,
combinando lo apilado
uno por uno en la respuesta.

Apila al bajar, combina de vuelta desde el suelo. (mul(4) = 4x3x2x1 = 24)

Al bajar, la respuesta está oculta,
lo que puede frustrar un poco.
Pero en cuanto toca el suelo,
se deshace suave en reversa.
Mientras más apilado,
más por combinar al subir.
Así que si se apila muy hondo
se vuelve pesado,
pero esa es historia para después.

Uno con divide y vencerás

Recuerda la lección pasada.
Partimos un problema grande a la mitad,
resolvimos cada parte y unimos.
Ese "partir y resolver cada parte"
es en realidad recursión.
resolver(8)
llama a resolver(4) y resolver(4),
y esos 4 a su vez
llaman a resolver(2).

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

Así que divide y vencerás y recursión
no son aparte; son lo mismo.
Partir = llamarse a sí mismo otra vez.
Cuando una pieza se vuelve tan chica
que no se puede partir, ese es el suelo,
y las respuestas chicas uniéndose hacia arriba
son el apilarse y deshacerse.
Todo lo que vimos se junta aquí.

La recursión, en una línea

La recursión tiene tres pilares.
Se llama con una entrada más chica,
tiene un suelo para parar,
y se apila y luego se deshace de vuelta.
Con solo estos tres,
hasta un problema que parece complejo
se le puede pasar discretamente
a "una versión más chica de sí mismo" y resolverlo.

Los tres pilares en orden. (se llama → un suelo para parar → se apila, se deshace)

Solo una cosa a la que estar atento.
Al partir, a veces el mismo problema chico
se resuelve una y otra vez.
Sacar la misma respuesta repetidamente
desperdicia tiempo.
Hay un truco de anotar una respuesta una vez
y reutilizarla,
y esa es justamente la próxima historia.