Recursión y la pila de llamadas
Una función que se llama a sí misma sobre un problema más chico.
Corre sobre la pila de llamadas — un stack que no administras a mano.
Dos partes obligatorias
- Caso base — el problema más chico, contestado de inmediato (la detiene)
- Caso recursivo — achica a instancias más pequeñas, combina
- Sin caso base → corre para siempre. Sin achicar → nunca llega a él.
- Cada llamada = un frame en la pila de llamadas → espacio O(depth)
Mira a Hanói resolverse solo
Mueve n−1 a un lado · mueve el disco grande · regresa los n−1.
Confía en la recursión para el problema más chico.
Costo exponencial
T(n)=2T(n−1)+1=2n−1
64 discos = 2⁶⁴−1 ≈ 585 mil millones de años. Los monjes están a salvo.
Recursión vs iteración
- La recursión trae overhead de llamadas + un límite de profundidad (Python ~1000)
- Toda recursión tiene un gemelo iterativo o con stack explícito
- Prefiere el loop cuando sea igual de claro; recurre en problemas autosimilares
Para llevar
Resuelve el problema más chico confiando en la recursión.
Es un stack disfrazado. Sigue: los sorts de divide y vencerás.