Recursividad: funciones que se llaman a sí mismas

Una función recursiva resuelve un problema resolviendo una versión más pequeña del mismo problema, hasta llegar a un caso tan simple que se responde directamente. Suena raro; con la pila de llamadas delante se ve claro.

Las dos partes de toda recursión

• Caso base: la condición que corta la recursión. Sin él, la función se llama para siempre → stack overflow.
• Caso recursivo: la función se llama a sí misma con un problema más pequeño, acercándose al caso base.

function factorial(n) {
  if (n <= 1) return 1;            // caso base
  return n * factorial(n - 1);     // caso recursivo
}

Visualizador de la pila de llamadas

Cada llamada pendiente es un marco apilado. Cuando una llamada devuelve, su marco se quita y el de abajo continúa. Elige una función y pulsa Ejecutar:

Cuidado con Fibonacci recursivo

fib(n) = fib(n-1) + fib(n-2) es elegante pero recalcula lo mismo una y otra vez: es O(2ⁿ). fib(40) ya tarda segundos. Se arregla guardando resultados (memoización) o con un bucle:

function fib(n, memo = {}) {
  if (n < 2) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);   // ahora O(n)
}

Recursividad vs bucle

Todo lo recursivo se puede escribir con un bucle y viceversa. La recursión brilla cuando la estructura del problema ya es recursiva: árboles, carpetas dentro de carpetas, dividir y vencer.

# Recorrer una carpeta y sus subcarpetas: natural con recursión
import os

def listar(ruta, nivel=0):
    for nombre in sorted(os.listdir(ruta)):
        completa = os.path.join(ruta, nombre)
        print("  " * nivel + nombre)
        if os.path.isdir(completa):
            listar(completa, nivel + 1)   # el mismo problema, una carpeta más adentro

Comprueba lo aprendido

Siguiente paso

Estructuras de datos visualizadas · Big-O · Algoritmos