Recursión en C: caso base, pila de llamadas y versión iterativa

​

Lo que vas a aprender

• Las partes de un diseño recursivo: caso base, caso general y combinación.
• Las fases de descenso y ascenso.
• La pila de llamadas y el árbol de llamadas.
• Los tipos de recursión: lineal, final y múltiple.
• Cómo transformar una función recursiva en iterativa.

​

Cómo se usa el simulador

• Elige la función: potencia, factorial, semifactorial, MCD, Fibonacci o suma de un vector.
• Elige la versión recursiva o iterativa.
• Ajusta los parámetros y avanza con ⏮, ◀, ▶ Ejecutar, ▶ y ⏭.
• Se ven el código con la línea actual y la fase (descenso o ascenso), la pila de llamadas, el árbol de llamadas (en ejecución, en espera o terminadas) y los contadores de llamadas y tamaño máximo de la pila.

​

Fundamentos teóricos

​

Diseño recursivo

1. Caso base: un caso tan sencillo que se resuelve directamente.
2. Caso general: reduce el problema a uno más pequeño del mismo tipo.
3. Combinación: construye el resultado a partir del de la llamada.

int potencia(int a, int n) {
    if (n == 0) return 1;              // caso base
    return potencia(a, n - 1) * a;     // caso general y combinación
}

​

Descenso y ascenso

• Descenso: se van apilando llamadas, cada una esperando a la siguiente, hasta el caso base.
• Ascenso: cada llamada recibe el resultado de la siguiente, aplica la combinación y devuelve el suyo.

​

Tipos de recursión

​

Coste

• Lineal: $n$ llamadas y pila de profundidad $n$.
• Fibonacci recursivo ingenuo: el número de llamadas crece exponencialmente ($\approx 1{,}6^n$), porque recalcula muchas veces los mismos valores.

​

De recursiva a iterativa

• Recursión final: basta un bucle que actualice los parámetros.
• No final: un bucle de descenso hasta el caso base y otro de ascenso que aplica la combinación (o calcular directamente de abajo arriba).

int mcd(int a, int b) {          // recursiva final
    if (b == 0) return a;
    return mcd(b, a % b);
}
int mcd_it(int a, int b) {       // iterativa
    while (b != 0) { int r = a % b; a = b; b = r; }
    return a;
}

​

Ejemplos resueltos

​

Experimenta con el simulador

​

Errores frecuentes

• Olvidar el caso base o que el caso general no se acerque a él: desbordamiento de pila.
• Usar Fibonacci recursivo para valores grandes.
• Confundir recursión final con no final.

​

Herramientas relacionadas