Recursión
La recursión (Recursion) es una técnica de programación en la que una función se llama a sí misma directa o indirectamente durante su definición o ejecución. La idea central es descomponer un problema complejo en subproblemas más pequeños pero con la misma estructura.
Conceptos básicos de la recursión
fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 3 × 2 × 1 × 1 = 6
Recuadro naranja (caso base) → detener la recursión y comenzar el retorno | Los marcos de pila se extraen en orden LIFO: el último en entrar es el primero en retornar
Una función recursiva válida debe incluir dos elementos clave:
| Elemento | Significado | Ejemplo (factorial) |
|---|---|---|
| Caso base | Condición para terminar la recursión, evita la recursión infinita | if (n == 0) return 1; |
| Caso recursivo | Descomponer el problema en subproblemas más pequeños y llamarse a sí misma | return n * factorial(n-1); |
Problemas clásicos de recursión
Factorial
Ejemplo
/* Implementación recursiva del factorial
n! = n × (n-1)!, caso base: 0! = 1 */
long long factorial(int n) {
if (n == 0) return 1; /* Caso base */
return n * factorial(n - 1); /* Caso recursivo */
}
int main() {
printf("5! = %lld\n", factorial(5)); /* Salida: 120 */
return 0;
}
Sucesión de Fibonacci
Ejemplo
/* Recursión ingenua: muchos cálculos repetidos, O(2ⁿ) */
int fib(int n) {
if (n <= 1) return n; /* Caso base */
return fib(n-1) + fib(n-2); /* Caso recursivo */
}
/* Optimización con memoización: almacena en caché los resultados calculados, O(n) */
#define MAX 100
long long memo[MAX] = {0};
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != 0) return memo[n]; /* Ya calculado, retorno directo */
memo[n] = fibMemo(n-1) + fibMemo(n-2);
return memo[n];
}
int main() {
printf("fib(10) (ingenua): %d\n", fib(10)); /* Salida: 55 */
printf("fibMemo(50) (memoización): %lld\n", fibMemo(50)); /* Salida: 12586269025 */
return 0;
}
Problema de las Torres de Hanói
Ejemplo
/* Resolución recursiva de las Torres de Hanói
mover n discos de src a dst con ayuda de aux
Pasos: n-1 de src→aux, el más grande de src→dst, n-1 de aux→dst */
void hanoi(int n, char src, char aux, char dst) {
if (n == 1) {
printf("Disco 1 de %c a %c\n", src, dst);
return;
}
hanoi(n - 1, src, dst, aux); /* Mover n-1 de src a aux */
printf("Disco %d de %c a %c\n", n, src, dst);
hanoi(n - 1, aux, src, dst); /* Mover n-1 de aux a dst */
}
int main() {
printf("Torres de Hanói (3 discos):\n");
hanoi(3, 'A', 'B', 'C');
/* Salida: 7 pasos en total (2³-1), número mínimo de pasos = 2ⁿ-1 */
return 0;
}
Comparación entre recursión e iteración
| Dimensión | Recursión | Iteración |
|---|---|---|
| Legibilidad del código | Alto(Cercano a la definición matemática) | A veces menos intuitivo que la recursión |
| Eficiencia de ejecución | Baja(Gastos generales del marco de pila) | Alta |
| Costo de espacio | Espacio de pila O(profundidad de recursión) | O(1) |
| Riesgo de desbordamiento de pila | tener(Cuando la profundidad es demasiado grande) | Ninguno |
| Estructura adecuada | Estructuras naturalmente recursivas como árboles y grafos | Estructuras lineales como los arrays |
Otras extensionesRecursión de colaEs una forma especial de recursión en la que la llamada recursiva es la última operación ejecutada en el cuerpo de la función. Algunos compiladores pueden optimizar la recursión de cola, transformándola en una iteración equivalente para ahorrar espacio de pila. Sin embargo, no todos los compiladores de C tienen esta optimización habilitada por defecto.