Recursion: functions that call themselves

A recursive function solves a problem by solving a smaller version of the same problem, until it reaches a case so simple it answers directly. It sounds odd; with the call stack in front of you it becomes clear.

The two parts of every recursion

• 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
}

Call stack visualiser

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:

Careful with recursive Fibonacci

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)
}

Recursion vs loop

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

Check what you've learned

Next step

Data structures visualised · Big-O · Algorithms