Recursividad en Lenguaje C: explicación y ejemplo

Recursividad en Lenguaje C: explicación y ejemplo

Una función recursiva es una función que se llama a sí misma. Se usa cuando un problema se puede expresar en versiones más pequeñas de sí mismo, y se apoya en la idea de que cada llamada resuelve un caso que ya no necesita descomponerse.

Toda función recursiva necesita exactamente dos cosas: un caso base, que devuelve un valor y detiene el proceso, y un caso recursivo, que avanza un paso hacia el caso base. Sin caso base, la función se llama para siempre.

Las dos partes de una función recursiva

Ejemplo 1: factorial

#include <stdio.h>

long factorial(int n);

long factorial(int n) {
    if (n == 0) {          /* caso base */
        return 1;
    }
    return n * factorial(n - 1);  /* caso recursivo */
}

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

La salida:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720

El caso base es n == 0, porque el factorial de cero vale uno por definición. El caso recursivo multiplica por n y pide el factorial del número anterior. Al bajar de 6 a 0, la recursión se detiene.

Cómo funciona por dentro

Cada llamada apila su propio marco, y el valor se devuelve al subir por la pila de llamadas:

factorial(3)
  = 3 * factorial(2)
  = 3 * (2 * factorial(1))
  = 3 * (2 * (1 * factorial(0)))
  = 3 * (2 * (1 * 1))   -> 6

Esto explica el orden de las líneas. La declaración long factorial(int n); antes de main es necesaria porque C evalúa de arriba hacia abajo y todavía no conoce la función cuando lee main.

Ejemplo 2: recorrido de un árbol binario

#include <stdio.h>

typedef struct Nodo {
    int valor;
    struct Nodo *izq;
    struct Nodo *der;
} Nodo;

void inorden(Nodo *raiz) {
    if (raiz == NULL) {         /* caso base: no hay nodo */
        return;
    }
    inorden(raiz->izq);         /* caso recursivo: subárbol izquierdo */
    printf("%d ", raiz->valor);
    inorden(raiz->der);         /* caso recursivo: subárbol derecho */
}

Aquí el caso base no es un valor, es una ausencia: raiz == NULL. Cada subárbol se recorre con la misma función, así que el código no se repite. Es el ejemplo donde la recursividad se nota más natural.

Recursión o iteración

Para recorrer una lista enlazada de mil millones de elementos, un while es la opción correcta. Para recorrer un árbol, la recursión es la opción legible. No es que una gane siempre: es que cada una resuelve mejor un tipo de problema.

Errores que hay que evitar

1. Olvidar el caso base. El programa termina con un error de desbordamiento de pila, no con un valor. Cuando se duda, se escribe primero la condición de salida.
2. No acercarse al caso base. Si en el caso recursivo se resta 1, esos mil elementos necesitan mil niveles de pila. Restar la mitad evita el problema.
3. Copiar los datos en cada llamada. Si el parámetro es un arreglo grande, se duplica la memoria por cada nivel. Pasar el puntero lo evita.
4. Confundir lo que se calcula con lo que se guarda. Si solo se necesita el resultado final, conviene devolver el valor; si se necesita todo el árbol, el caso base debe imprimir o acumular.

La recursividad no es un tema de teoría: es la forma más corta de expresar problemas que se contienen a sí mismos. Un árbol genealógico, una lista de nodos o un árbol de búsqueda binaria comparten la misma estructura: un caso que termina y un paso que reduce el problema.

© Arturo Juárez Monroy