> ## Documentation Index
> Fetch the complete documentation index at: https://apuntes.simulab.es/llms.txt
> Use this file to discover all available pages before exploring further.

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

> La recursión explicada paso a paso en C: caso base y caso general, descenso y ascenso, pila y árbol de llamadas, recursión lineal, final y múltiple (Fibonacci) y cómo pasar a iterativa.

<Card title="Abrir el simulador" icon="flask" href="https://simulab.es/programacion/recursion">
  Potencia, factorial, MCD, Fibonacci y suma de un vector: pila y árbol de llamadas, y su versión iterativa.
</Card>

Una función **recursiva** se llama a sí misma con un problema más pequeño. Bien usada, permite escribir soluciones muy cortas a problemas que serían enrevesados con bucles. Pero para entenderla hay que ver **qué pasa en la pila** con cada llamada. Este simulador lo muestra paso a paso, junto con el árbol de llamadas y la versión iterativa equivalente.

## 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.

```c theme={null}
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

| Tipo | Característica | Ejemplo |
| - | - | - |
| Lineal no final | Una llamada; tras volver aún hay que operar | Potencia, factorial |
| Lineal final | La llamada es lo **último** que se hace | MCD de Euclides |
| Múltiple | Varias llamadas en cada caso general | Fibonacci |

### 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).

```c theme={null}
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

<AccordionGroup>
  <Accordion title="Ejemplo 1 · potencia(2, 3)" defaultOpen>
    Descenso: potencia(2, 3) → (2, 2) → (2, 1) → (2, 0). Caso base: 1.

    Ascenso: $1 \cdot 2 = 2$; $2 \cdot 2 = 4$; $4 \cdot 2 = 8$. 4 llamadas, pila máxima de 4 marcos.
  </Accordion>

  <Accordion title="Ejemplo 2 · Factorial">
    $5! = 5 \cdot 4! = 5 \cdot 4 \cdot 3! = \dots = 120$, con caso base $0! = 1$.
  </Accordion>

  <Accordion title="Ejemplo 3 · Fibonacci">
    fib(5) con $\text{fib}(n) = \text{fib}(n-1) + \text{fib}(n-2)$ y casos base fib(0) = 0, fib(1) = 1 hace **15 llamadas**: fib(3) se calcula dos veces y fib(2), tres.
  </Accordion>

  <Accordion title="Ejemplo 4 · MCD">
    mcd(84, 60) → mcd(60, 24) → mcd(24, 12) → mcd(12, 0) = 12. Como es final, el resultado sube sin operar.
  </Accordion>
</AccordionGroup>

## Experimenta con el simulador

<Steps>
  <Step title="La pila">
    Con potencia, sube n y mira el tamaño máximo de la pila.
  </Step>

  <Step title="Fibonacci">
    Con Fibonacci, pasa de n = 4 a n = 8. ¿Cuánto crece el número de llamadas?
  </Step>

  <Step title="Iterativa">
    Cambia a la versión iterativa del factorial y compara.
  </Step>
</Steps>

## 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

<CardGroup cols={3}>
  <Card title="Divide y vencerás" icon="code-branch" href="/programacion/c/divide-y-venceras">
    Recursión que parte el problema.
  </Card>

  <Card title="Backtracking" icon="code-branch" href="/programacion/c/backtracking">
    Recursión que explora.
  </Card>

  <Card title="Memoria y punteros" icon="memory" href="/programacion/c/punteros">
    La pila por dentro.
  </Card>
</CardGroup>


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.