Recurrencia

La recursión es una técnica en la que una función resuelve un problema llamándose a sí misma con una versión más pequeña del mismo problema.

Cada llamada simplifica un poco el problema… hasta llegar a uno tan simple que se resuelve sin volver a llamarse.

Abrís una muñeca y aparece otra adentro… y otra. No sabés cuántas hay hasta llegar a la más chica, la que ya no contiene ninguna. Esa incertidumbre es la recursión: explorás hacia adentro hasta tocar el caso base.

def factorial(n):
  if n == 0:        # caso base
    return 1
  return n * factorial(n - 1)  # caso recursivo

Cada factorial(n) queda en pausa esperando a la siguiente. Se apilan hasta el caso base; luego se devuelven los valores de adentro hacia afuera.

def suma(lista):
  if lista == []:        # caso base
    return 0
  return lista[0] + suma(lista[1:])

La suma de una lista es su primer elemento más la suma del resto. La lista vacía es el caso base: suma 0.

Cuando una función llama a otra, la actual se pausa. Python guarda su estado en una “cajita” —el stack frame— con todo lo que necesita para retomar después.