Un algoritmo recursivo es aquel que se llama a sí mismo como parte de su solución. A diferencia de los iterativos —que se analizan línea por línea—, los recursivos se siguen a través de ambientes de ejecución, también llamados marcos de pila.

La recursión está en la naturaleza: las muñecas rusas, los fractales, la definición del factorial. Su poder está en expresar soluciones complejas de forma elegante y concisa.

Cada vez que un algoritmo recursivo se llama a sí mismo, el sistema crea un nuevo ambiente de ejecución y lo apila sobre los anteriores.

En ese ambiente se guardan:

• Todos los parámetros recibidos en esa llamada.
• Todas las variables locales declaradas en esa ejecución.
• La dirección de retorno: el punto exacto del código al que hay que volver cuando esa llamada termine.

Mientras el ambiente no termine, todos los ambientes anteriores quedan suspendidos esperando en la pila. Por eso la recursión tiene un costo espacial relevante: cada ambiente consume memoria.

Todo algoritmo recursivo correcto tiene exactamente dos partes:

Estructura obligatoria de un algoritmo recursivo

Fibonacci es la suma de los dos anteriores: $Fib(n)=Fib(n-1)+Fib(n-2)$. En Fibonacci, se requieren dos casos base no porque haya dos llamadas recursivas, sino porque la fórmula depende de dos valores iniciales.

Pseudocódigo

int Fib(E int n) {
  if (n=0) or (n=1) then
    f <- n # caso base: Fib(0)=0, Fib(1)=1
  else
    f <- Fib(n-1) + Fib(n-2) # caso general
  endif
  return f
}

Seguimiento con $n=5$: el algoritmo primero resuelve $Fib(4)$ (abre un ambiente), dentro de ese resuelve $Fib(3)$, y así hasta llegar a los casos base. El $Fib(n-2)$ de cada nivel queda pendiente hasta que el izquierdo termine.

Ecuación de recurrencia

Tres torres (origen, auxiliar, destino) y $n$ discos apilados de mayor a menor en el origen.

Estrategia recursiva: para mover $n$ discos del origen al destino:

1. Mover los $n-1$ discos superiores del origen al auxiliar, usando destino como apoyo.
2. Mover el disco más grande del origen al destino.
3. Mover los $n-1$ discos del auxiliar al destino, usando origen como apoyo.

Pseudocódigo

TH(E int n, E char o, E char a, E char d) {
  if (n = 1) then
    Print('mover disco del origen al destino') # caso base
  else
    TH(n-1, o, d, a) # mueve n-1 al auxiliar
    Print('mover disco del origen al destino')
    TH(n-1, a, o, d) # mueve n-1 al destino
  endif
}

Árbol de recursión: cada nivel del árbol tiene el doble de nodos que el anterior. Nivel 1 → $2^0$, Nivel 2 → $2^1$, Nivel 3 → $2^2$, Nivel $k$ → $2^{k-1}$. Cada nodo cuesta una constante: un movimiento.

Antes de elegir el método de resolución, hay que identificar qué tipo de ecuación tenemos:

Una recursión es de cola cuando el llamado recursivo es lo último que ocurre en el caso general. En ese caso, el sistema puede convertirla en iteración automáticamente o manualmente porque no hay nada pendiente después del llamado.