Recursión paso a paso
Sigue cada llamada en el código, la pila y el árbol de llamadas. Cambia a la versión iterativa para ver cómo se transforma.
1int potencia(int a, int n)2{3 if (n == 0)4 return 1; // caso base5 else6 return potencia(a, n - 1) * a; // caso general7}¿n == 0? No, n = 4.
- potencia(2, 4)
aⁿ = aⁿ⁻¹ · a, y a⁰ = 1. Cada llamada reduce n en 1 hasta llegar al caso base; luego, al volver, cada nivel multiplica por a.
Lineal no final: tras volver de la llamada aún hay que multiplicar por a.
Una función recursiva se llama a sí misma con un problema más pequeño hasta llegar a un caso base que se resuelve directamente. Todo diseño recursivo tiene un caso base, un caso general que reduce el problema y una función de combinación que construye el resultado a partir del de la llamada.
Al ejecutarse hay dos fases. En el descenso se van apilando llamadas, cada una esperando a la siguiente. Al llegar al caso base empieza el ascenso: cada llamada recibe el resultado, aplica la combinación y devuelve el suyo a la anterior.
La versión iterativa hace lo mismo sin pila de llamadas. Si la recursión es final (la llamada es lo último que se hace, como en el MCD), basta un bucle. Si no es final, se usa un bucle de descenso hasta el caso base y otro de ascenso que aplica la combinación.
Sigue potencia(2, 3) con potencia(a, n) = potencia(a, n − 1) · a y potencia(a, 0) = 1.
- Descenso: potencia(2, 3) llama a potencia(2, 2), que llama a potencia(2, 1), que llama a potencia(2, 0).
- Caso base: potencia(2, 0) devuelve 1.
- Ascenso: potencia(2, 1) = 1 · 2 = 2; potencia(2, 2) = 2 · 2 = 4; potencia(2, 3) = 4 · 2 = 8.
- Ha habido 4 llamadas y la pila ha llegado a tener 4 marcos.
potencia(2, 3) = 8
Preguntas frecuentes
¿Qué pasa si una función recursiva no tiene caso base?
Se llama a sí misma sin fin hasta que la pila se llena y el programa termina con un desbordamiento de pila (stack overflow). Lo mismo ocurre si el caso general no acerca los parámetros al caso base.
¿Qué es la recursión final?
La que hace la llamada recursiva como última operación y devuelve su resultado sin tocarlo, como mcd(a − b, b). Se transforma en un bucle directamente, sin fase de ascenso.
¿Por qué Fibonacci recursivo es tan lento?
Cada llamada hace dos, y los mismos valores se calculan una y otra vez: el número de llamadas crece de forma exponencial. La versión iterativa guarda los dos últimos términos y es lineal.
¿Es mejor la versión recursiva o la iterativa?
La recursiva suele ser más fácil de escribir y de demostrar correcta. La iterativa ahorra la memoria de la pila y el coste de las llamadas. Con la misma estrategia, las dos tienen el mismo orden de complejidad.