¿Qué es la recursión?

Question

Accepted Answer

**Recursión** es cuando una función se llama a sí misma para resolver una versión más pequeña del mismo problema. Toda recursión necesita un **caso base (base case)** que la detiene y un **caso recursivo (recursive case)** que avanza hacia el caso base.

## La idea

Divide un problema en subproblemas idénticos más pequeños. Cada llamada empuja un marco en la **pila de llamadas (call stack)**; los retornos los sacan.

## Ejemplo

```python
def factorial(n):
    if n <= 1:            # base case: stop recursing
        return 1
    return n * factorial(n - 1)   # recursive case: smaller problem

factorial(4)             # 4 * 3 * 2 * 1 -> 24
```

## Seguimiento

```text
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
```

## Complejidad

Aquí **O(n)** tiempo y **O(n)** espacio de pila (un marco por llamada).

## Peligros

- **Caso base faltante** -> recursión infinita -> desbordamiento de pila.
- La recursión profunda puede agotar la pila; algunos lenguajes carecen de optimización tail-call.
- Recalcular subproblemas superpuestos puede elevarse a tiempo exponencial (corrígelo con memoización).

## Por qué es importante

La recursión expresa naturalmente problemas auto-similares — árboles, grafos, divide y conquista — mucho más limpiamente que los bucles.

Es el modelo mental detrás de merge sort, backtracking y programación dinámica.

Comprender la pila de llamadas también te hace mejor en depuración y razonamiento sobre memoria.