Docs ejecutables de C: Recursión

Q: ¿Qué es la recursión en C?

Una función que se llama a sí misma para resolver una versión más pequeña del mismo problema. Toda función recursiva necesita dos cosas: un caso base que retorna sin volver a llamarse, y un caso recursivo que se acerca de forma medible a él. Sin el caso base las llamadas nunca paran y el programa revienta con un desbordamiento de pila.

Q: ¿Cómo se escribe una función factorial en C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. El caso base atiende el 0 y el 1, y cada llamada recursiva reduce n en uno hasta alcanzarlo. Ten en cuenta que un int se desborda en 13!: usa unsigned long long para valores mayores.

Q: ¿Por qué el Fibonacci recursivo es tan lento en C?

Porque fib(n) llama a fib(n-1) y a fib(n-2), que recalculan los mismos subproblemas una y otra vez: la cantidad de llamadas crece de forma exponencial, así que fib(50) tardaría años. Reescribirlo como un bucle que guarda los dos últimos valores lo vuelve lineal e instantáneo.

Q: ¿Qué causa un desbordamiento de pila en la recursión en C?

Cada llamada ocupa un marco de memoria en la pila para sus parámetros y sus locales, y la pila solo tiene unos pocos megabytes. Un caso base ausente o inalcanzable significa recursión infinita y un fallo inmediato; incluso una recursión correcta que baje cientos de miles de niveles puede agotar la pila.

Una función que se llama a sí misma

Nada impide que una función de C se llame a sí misma. Su propio nombre está en ámbito dentro de su cuerpo, así que esto es legal:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* se llama a si misma, pero nunca se detiene! */
}

También está rota. Imprime para siempre, hacia los números negativos, hasta que el programa revienta. Lo que le falta es un caso base: una condición bajo la cual la función retorna sin llamarse a sí misma.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* caso base: detenerse */
        printf("Despegue!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* caso recursivo: un problema mas pequeno */
}

int main(void) {
    countdown(5);
    return 0;
}

Toda función recursiva tiene exactamente estas dos partes:

Un caso base: la entrada más pequeña, respondida directamente, sin más llamadas.
Un caso recursivo: resuelve el problema en términos de una versión estrictamente más pequeña de sí mismo.

"Estrictamente más pequeña" es la parte en la que la gente se equivoca. countdown(n - 1) avanza hacia 0 en cada llamada. countdown(n) no lo haría, ni tampoco countdown(n / 2) si n pudiera quedarse en 1 para siempre. Todo camino debe encoger el problema, o el caso base nunca se alcanza.

Factorial

El primer ejemplo estándar. n! es n × (n-1) × ... × 1, y 0! está definido como 1. Esa definición ya es recursiva: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* caso base: 0! y 1! son ambos 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* caso recursivo */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Sigue factorial(4) para ver cómo se arma la respuesta. Las llamadas bajan, y las multiplicaciones ocurren en el camino de vuelta:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (caso base)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

No se multiplica nada hasta que el caso base retorna. Cada llamada pendiente queda esperando, guardando su propio n, que es el punto que vale la pena interiorizar: esas llamadas en espera ocupan memoria.

Fíjate en el tipo de retorno. Un int se desborda alrededor de 13!, produciendo en silencio un número equivocado: C no comprueba nada. unsigned long long te lleva hasta 20! y no más allá, porque 21! excede los 64 bits. La recursión no es el factor limitante aquí; el tipo lo es.

El caso base usa n <= 1 en vez de n == 1 a propósito: factorial(0) debería ser 1, y el <= lo atiende. Con n == 1, llamar a factorial(0) recurriría a -1, -2 y nunca terminaría: una buena ilustración de cómo un caso base "obviamente correcto" puede olvidarse de una entrada.

Fibonacci, y por qué la versión ingenua es una trampa

Fibonacci es el otro clásico: cada número es la suma de los dos anteriores, empezando en 0 y 1. La definición recursiva se escribe sola.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld llamadas)\n", n, result, calls);
    }
    return 0;
}

Mira los conteos de llamadas. fib(10) toma 177 llamadas; fib(35) toma casi 30 millones. Cada paso de 5 multiplica el trabajo por unas once veces.

La razón se ve en el árbol de llamadas. fib(5) llama a fib(4) y a fib(3); fib(4) llama a fib(3) otra vez; y cada uno de esos recalcula fib(2) desde cero. Nada se recuerda, así que los mismos subproblemas se resuelven una y otra vez, y la cantidad de llamadas crece aproximadamente como 1.6ⁿ. fib(50) así correría durante días; fib(100) sobreviviría al universo.

La versión con bucle guarda los dos últimos valores y es lineal:

#include <stdio.h>

long long fibFast(int n) {
    if (n < 2) {
        return n;
    }
    long long prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        long long next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) retorna al instante. La lección no es "la recursión es lenta": es que la recursión con subproblemas solapados es lenta salvo que recuerdes las respuestas. Guarda los resultados en un array mientras los calculas (memoización) y la versión recursiva también se vuelve lineal.

La pila de llamadas y el desbordamiento de pila

Toda llamada a función necesita un sitio donde guardar sus parámetros, sus locales y la dirección a la que volver. Ese almacenamiento es un marco de pila, apilado cuando la llamada empieza y desapilado cuando retorna. La recursión apila marcos uno encima de otro: factorial(1000) tiene mil marcos vivos a la vez, cada uno con su propio n.

La pila no es grande. Un valor típico por defecto es de 1 a 8 MB, así que unas pocas decenas de miles de marcos es el límite realista, y mucho menos si cada marco guarda un array local grande. Excédelo y el programa muere:

Segmentation fault (core dumped)

Eso es un desbordamiento de pila, y hay dos formas de conseguirlo:

Recursión infinita: un caso base ausente o inalcanzable. Esto es un error, y el fallo es inmediato.

int bad(int n) {
    return bad(n - 1);      /* sin caso base: revienta en una fraccion de segundo */
}

Correcta pero demasiado profunda: recurrir una vez por elemento sobre una lista de un millón de ítems. La lógica está bien; el enfoque no cabe en la pila. Reescríbelo como un bucle, o reestructúralo para que la profundidad sea logarítmica (recurrir sobre mitades, como hacen la búsqueda binaria y el merge sort, da una profundidad de unos 20 para un millón de ítems).

Algunos compiladores pueden convertir la recursión de cola —donde la llamada recursiva es lo último que hace la función, sin trabajo pendiente después— en un bucle, reutilizando un solo marco. El countdown de arriba es recursivo de cola; factorial no, porque la multiplicación todavía tiene que ocurrir después de que la llamada retorne. Pero C no exige esta optimización, así que puede ocurrir o no según el compilador y las banderas. Nunca escribas C que solo funcione porque el optimizador eliminó una llamada de cola.

Dónde gana de verdad la recursión

Toda función recursiva puede reescribirse como un bucle, y para un conteo simple el bucle es claramente mejor. La recursión se gana su lugar cuando los datos mismos son recursivos, cuando una estructura contiene copias más pequeñas de sí misma.

La búsqueda binaria es un ejemplo limpio: busca en la mitad, luego en la mitad de esa.

#include <stdio.h>

/* devuelve el indice de target, o -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* caso base: no queda nada */
    }
    int mid = low + (high - low) / 2;       /* evita el desbordamiento con indices grandes */

    if (a[mid] == target) {
        return mid;                         /* caso base: encontrado */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> indice %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Aquí hay dos casos base, lo cual es normal: uno para el éxito y otro para el agotamiento. La profundidad es de unos log₂(n), así que incluso mil millones de elementos necesitan solo treinta marcos.

Otros lugares donde la recursión encaja de forma natural: recorrer un árbol o una lista enlazada, recorrer directorios, analizar expresiones anidadas y los ordenamientos de divide y vencerás como quicksort y merge sort. En todos ellos el código recursivo es más corto y más claro que el bucle con una pila explícita que lo reemplazaría.

¿Recursión o bucle?

Usa un bucle cuando       el problema es lineal: contar, sumar, recorrer
Usa recursion cuando      los datos son anidados: arboles, estructuras anidadas, divide y venceras
Reescribe la recursion    si la profundidad puede crecer sin limite con el tamano de la entrada
Nunca uses recursion      cuando los subproblemas se solapan, salvo que memorices resultados

Dos notas prácticas. Las llamadas recursivas cuestan un poco más que una iteración de bucle —un marco que apilar y desapilar cada vez— así que en bucles calientes y simples la versión iterativa gana en velocidad además de en memoria. Y depurar es distinto: una traza de una recursión profunda son cientos de marcos de aspecto idéntico, así que imprime el parámetro al entrar (como hace el contador calls de arriba) cuando algo no esté terminando.

Escribir una función recursiva: una lista de comprobación

Encuentra primero el caso base. ¿Cuál es la entrada más pequeña y cuál es su respuesta? Si no puedes nombrarla, la función no se puede escribir.
Da por hecho que la llamada recursiva funciona. No la sigas mentalmente: confía en que factorial(n - 1) devuelve (n-1)! y escribe el único paso que lo convierte en la respuesta.
Comprueba que todo camino encoge. Cada llamada recursiva debe avanzar hacia el caso base para toda entrada posible, incluidos el 0 y los negativos.
Comprueba la profundidad. ¿Aproximadamente cuántos marcos de profundidad alcanzará esto con datos reales? Miles está bien; millones no.
Comprueba el solapamiento. Si el mismo subproblema se calcula dos veces, necesitas memoización o un bucle.

Preguntas frecuentes

¿Qué es la recursión en C?

Una función que se llama a sí misma para resolver una versión más pequeña del mismo problema. Toda función recursiva necesita dos cosas: un caso base que retorna sin volver a llamarse, y un caso recursivo que se acerca de forma medible a él. Sin el caso base las llamadas nunca paran y el programa revienta con un desbordamiento de pila.

¿Cómo se escribe una función factorial en C?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. El caso base atiende el 0 y el 1, y cada llamada recursiva reduce n en uno hasta alcanzarlo. Ten en cuenta que un int se desborda en 13!: usa unsigned long long para valores mayores.

¿Por qué el Fibonacci recursivo es tan lento en C?

Porque fib(n) llama a fib(n-1) y a fib(n-2), que recalculan los mismos subproblemas una y otra vez: la cantidad de llamadas crece de forma exponencial, así que fib(50) tardaría años. Reescribirlo como un bucle que guarda los dos últimos valores lo vuelve lineal e instantáneo.

¿Qué causa un desbordamiento de pila en la recursión en C?

Cada llamada ocupa un marco de memoria en la pila para sus parámetros y sus locales, y la pila solo tiene unos pocos megabytes. Un caso base ausente o inalcanzable significa recursión infinita y un fallo inmediato; incluso una recursión correcta que baje cientos de miles de niveles puede agotar la pila.

Conceptos relacionados