Capítulo 11 (pp. 203–210) de Computer Science I.

Temas

Ideas Clave

• Toda recursión necesita un caso base y progreso hacia él.
• Recursión de cola — la llamada recursiva es la última acción; puede optimizarse a iteración.
• Memoización — cachear resultados para evitar recálculos (p. ej. Fibonacci).
• La cobertura es intencionalmente superficial a nivel de CS1. Recapitulada brevemente en cada parte de lenguaje (C, Java, PHP).

Ejemplos

Factorial (caso base + caso recursivo)

función factorial(n):
  si n ≤ 1:              // caso base
    retornar 1
  retornar n × factorial(n - 1)

Fibonacci con memoización

memo ← mapa vacío
función fib(n):
  si n < 2: retornar n
  si n en memo: retornar memo[n]
  memo[n] ← fib(n - 1) + fib(n - 2)
  retornar memo[n]

El cacheo convierte el trabajo exponencial en lineal.

En Java

static long factorial(int n) {
    if (n <= 1) return 1;               // caso base
    return n * factorial(n - 1);
}

static Map<Integer, Long> memo = new HashMap<>();
static long fib(int n) {
    if (n < 2) return n;
    if (memo.containsKey(n)) return memo.get(n);
    long v = fib(n - 1) + fib(n - 2);
    memo.put(n, v);
    return v;
}

Citas

[1] Computer Science I, Cap. 11, pp. 203–210.