Recursión
Última actualización
La recursión es una función que se llama a sí misma sobre una versión más pequeña del mismo problema, hasta llegar a un caso tan pequeño que puede responderse directamente. Ese caso que se responde directamente es el caso base, y toda función recursiva necesita uno: fib(n) se sigue dividiendo en fib(n - 1) y fib(n - 2) hasta llegar a fib(1) o fib(0), que simplemente se devuelven a sí mismos. El visualizador de arriba hace exactamente esto: pulsa reproducir y observa cómo las llamadas se ramifican en un árbol, alcanzan los casos base en las hojas y luego devuelven sus valores hacia arriba, combinándose en cada nivel.
Lo segundo que muestra la animación es la pila de llamadas: todas las llamadas que han empezado pero aún no han terminado. La pila crece a medida que las llamadas se hacen más profundas, alcanza su máximo en la profundidad de recursión y se deshace conforme vuelven los resultados; por eso una recursión profunda puede provocar un desbordamiento de pila mientras que un bucle iterativo nunca hace crecer la pila. La misma forma de llamadas está en el corazón de la búsqueda en profundidad, el merge sort y casi todas las operaciones sobre un árbol binario.
Complejidad temporal y espacial
Para el Fibonacci recursivo ingenuo que se muestra arriba, y sus dos correcciones habituales:
| Enfoque | Tiempo | Espacio | Notas |
|---|---|---|---|
| Recursión ingenua | O(2^n) | O(n) | El árbol de llamadas se duplica en cada nivel; el espacio es la pila más profunda, no el árbol entero. |
| Con memoización | O(n) | O(n) | Cada fib(k) se calcula una sola vez y se guarda en caché; los subárboles repetidos se reducen a simples consultas. |
| Bucle iterativo | O(n) | O(1) | Dos variables que van rotando sustituyen por completo a la pila. |
| Cualquier recursión, en general | llamadas × trabajo por llamada | O(max depth) | La pila guarda un marco por cada llamada que ha empezado pero no ha terminado. |
Paso a paso
| Paso | Qué ocurre |
|---|---|
| 1 | La primera llamada fib(n) entra en la pila de llamadas. |
| 2 | Necesita fib(n - 1), así que esa llamada también entra en la pila; la llamada padre espera. |
| 3 | Las llamadas se siguen anidando hasta que una pregunta por n <= 1: el caso base responde de inmediato, sin ninguna llamada más profunda. |
| 4 | El valor del caso base vuelve a su llamada padre, que ya puede iniciar su segunda llamada, fib(n - 2). |
| 5 | Cuando ambas llamadas hijas han devuelto su valor, el padre las suma y devuelve también; su marco sale de la pila. |
| 6 | El retorno se repite subiendo por el árbol hasta que el marco de la primera llamada sale con la respuesta final y la pila queda vacía. |
Ejemplo resuelto
Evaluando fib(4) en el orden exacto de las llamadas, tal como lo reproduce la animación:
| Llamada | Pila en ese momento | Devuelve |
|---|---|---|
fib(4) | fib(4) | espera a sus hijas |
fib(3) | fib(4) > fib(3) | espera a sus hijas |
fib(2) | fib(4) > fib(3) > fib(2) | espera a sus hijas |
fib(1) | fib(4) > fib(3) > fib(2) > fib(1) | 1 (caso base) |
fib(0) | fib(4) > fib(3) > fib(2) > fib(0) | 0 (caso base) |
fib(2) combina | fib(4) > fib(3) > fib(2) | 1 + 0 = 1 |
fib(1) | fib(4) > fib(3) > fib(1) | 1 (caso base) |
fib(3) combina | fib(4) > fib(3) | 1 + 1 = 2 |
fib(2) de nuevo | fib(4) > fib(2) | 1, recalculado desde cero |
fib(4) combina | fib(4) | 2 + 1 = 3 |
Cuándo usar la recursión
| Úsala cuando | Evítala cuando |
|---|---|
| El problema es autosemejante: árboles, estructuras anidadas, divide y vencerás | Un bucle simple expresa lo mismo sin marcos de pila |
La profundidad está acotada y es moderada, como O(log n) en el merge sort | La profundidad puede alcanzar el tamaño de la entrada en entradas enormes, con riesgo de desbordamiento de pila |
| El backtracking necesita la pila para recordar dónde retomar | Los mismos subproblemas se repiten y no estás guardando los resultados en caché |
| La versión recursiva es claramente más fácil de leer y de verificar | Estás en un bucle crítico donde el coste de cada llamada se nota de verdad |
Código de Recursion
Una implementación limpia y ejecutable de Recursion en Python, JavaScript, Java, C++, C. Elige un lenguaje, copia el código o ábrelo ya cargado en el Playground de Coddy.
Código de Recursion en Python
Python
1calls = 02
3def fib(n, depth=0):4 global calls5 calls += 16 # Print the call with its depth so the recursion is visible7 print(" " * depth + f"fib({n})")8 if n <= 1:9 return n10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)11
12
13print("fib(5) =", fib(5))14print("calls made:", calls)Código de Recursion en JavaScript
JavaScript
1let calls = 0;2
3function fib(n, depth = 0) {4 calls += 1;5 // Print the call with its depth so the recursion is visible6 console.log(' '.repeat(depth) + `fib(${n})`);7 if (n <= 1) return n;8 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);9}10
11console.log('fib(5) =', fib(5));12console.log('calls made:', calls);Código de Recursion en Java
Java
1public class Main {2 static int calls = 0;3
4 static int fib(int n, int depth) {5 calls++;6 // Print the call with its depth so the recursion is visible7 System.out.println(" ".repeat(depth) + "fib(" + n + ")");8 if (n <= 1) return n;9 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);10 }11
12 public static void main(String[] args) {13 System.out.println("fib(5) = " + fib(5, 0));14 System.out.println("calls made: " + calls);15 }16}Código de Recursion en C++
C++
1#include <iostream>2#include <string>3
4int calls = 0;5
6int fib(int n, int depth) {7 calls++;8 // Print the call with its depth so the recursion is visible9 std::cout << std::string(depth * 2, ' ') << "fib(" << n << ")\n";10 if (n <= 1) return n;11 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);12}13
14int main() {15 int result = fib(5, 0);16 std::cout << "fib(5) = " << result << "\n";17 std::cout << "calls made: " << calls << "\n";18 return 0;19}Código de Recursion en C
C
1#include <stdio.h>2
3int calls = 0;4
5int fib(int n, int depth) {6 calls++;7 /* Print the call with its depth so the recursion is visible */8 printf("%*sfib(%d)\n", depth * 2, "", n);9 if (n <= 1) return n;10 return fib(n - 1, depth + 1) + fib(n - 2, depth + 1);11}12
13int main(void) {14 printf("fib(5) = %d\n", fib(5, 0));15 printf("calls made: %d\n", calls);16 return 0;17}Preguntas frecuentes sobre la recursión
¿Qué es un caso base en recursión?
Es la entrada lo bastante pequeña como para responderse sin otra llamada recursiva. Para
fib(n) es n <= 1, que devuelve n directamente. Sin un caso base alcanzable las llamadas nunca terminan, la pila sigue creciendo y el programa se cae con un desbordamiento de pila.¿Qué es la pila de llamadas y por qué importa?
El entorno de ejecución guarda un marco por cada llamada que ha empezado pero aún no ha terminado, con sus argumentos y sus variables locales. La profundidad de recursión es igual a la altura de la pila, así que una recursión que baja
n niveles usa O(n) de memoria aunque cada llamada apenas haga trabajo. La fila de fichas bajo la animación muestra exactamente esta pila creciendo y deshaciéndose.¿Por qué el Fibonacci recursivo tarda tiempo exponencial?
Porque los mismos subproblemas se recalculan una y otra vez: en el ejemplo resuelto de arriba,
fib(2) se evalúa dos veces dentro de fib(4), y la duplicación se repite aproximadamente en cada nivel, lo que da O(2^n) llamadas. Guardar cada resultado en caché la primera vez que se calcula, lo que se conoce como memoización, reduce el árbol a O(n).¿Es mejor la recursión que la iteración?
Ninguna es mejor de forma universal. Toda recursión puede reescribirse como un bucle con una pila explícita, y todo bucle como una recursión. La recursión gana en legibilidad para problemas autosemejantes como el recorrido de árboles y la búsqueda en profundidad; la iteración gana en memoria y en coste de llamada para recorridos lineales.
¿Qué provoca un desbordamiento de pila en una función recursiva?
O bien un caso base ausente o inalcanzable, de modo que las llamadas nunca terminan, o bien una recursión correcta cuya profundidad es sencillamente demasiado grande para el límite de pila del entorno de ejecución, como recurrir una vez por elemento sobre una entrada de millones. Las soluciones son garantizar el caso base, acotar la profundidad o convertirla en iteración.
¿Qué algoritmos son recursivos por naturaleza?
Los ordenamientos de divide y vencerás como el merge sort y quicksort, los recorridos de un árbol binario y de grafos, la búsqueda binaria, los puzles de backtracking como las N reinas, y todo lo que se define sobre una estructura anidada, como JSON o un sistema de archivos.
Recursos relacionados
Más visualizaciones
