La recursión es una técnica en la que una función se llama a sí misma para resolver un problema dividiéndolo en subproblemas más pequeños. Es uno de los conceptos más importantes de la programación.
El caso base — la clave
Todo algoritmo recursivo necesita dos cosas: un caso base que detenga la recursión, y un caso recursivo que reduzca el problema.
Ejemplo: Factorial
def factorial(n):
if n <= 1: # Caso base
return 1
return n * factorial(n - 1) # Caso recursivo
print(factorial(5)) # 120Ejemplo: Fibonacci con memoización
from functools import lru_cache
@lru_cache(maxsize=None)
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(50)) # InstantáneoCuándo usar recursión
- Árboles y grafos (recorrido en profundidad)
- Divide y vencerás (Merge Sort, Quick Sort)
- Backtracking (Sudoku, laberintos, N-Reinas)
Cuidado con el stack overflow
Python tiene un límite de 1000 llamadas recursivas por defecto. Para recursiones muy profundas convierte el algoritmo a iterativo o usa sys.setrecursionlimit().