Recursión

Anatomía de una función recursiva

1. Caso base: condición de parada. Sin él → stack overflow.
2. Llamada recursiva: el problema se reduce en cada llamada.
3. Combinación: los valores se ensamblan al regresar.

Visualizando la recursión

factorial(4)
  └─ 4 * factorial(3)
          └─ 3 * factorial(2)
                  └─ 2 * factorial(1)
                          └─ 1  ← caso base

Retorna: 1 → 2 → 6 → 24

Memoización

Si la misma llamada recursiva se repite, guardar el resultado en un arreglo. Convierte O(2ⁿ) en O(n).

Cuándo usar recursión

• Problemas que se dividen en subproblemas iguales
• DFS en árboles y grafos
• Backtracking
• Divide y vencerás

Límite del stack

Para n > 10⁵ de profundidad, prefiere iterativo o usa memoización + iteración (DP bottom-up).