🧮 Computational Mathematics

Inicio · Parte 04 — Matemática discreta para computación

092 — Recurrencias

intermedio clase 12 de 20 4 horas demostración recurrences

Una recurrencia define cada término desde los anteriores; su coste depende radicalmente de si se memoiza.

Fórmulas

F(n) = F(n−1) + F(n−2),  F(0)=0, F(1)=1
Binet: F(n) = (φⁿ − (−1/φ)ⁿ)/√5,  φ = (1+√5)/2

Desarrollo

Una recurrencia es una definición autorreferente con casos base. Fibonacci es el ejemplo canónico, y sirve para ilustrar la diferencia más importante del análisis de algoritmos: la implementación recursiva ingenua recalcula los mismos valores una y otra vez y tarda O(φⁿ); la iterativa —o la memoizada— tarda O(n).

La diferencia no es de constante: para n = 50, la ingenua hace del orden de 10¹⁰ llamadas y la iterativa 50 pasos. Es la demostración más clara de que la complejidad asintótica no es una abstracción académica.

Fibonacci tiene además una fórmula cerrada, la de Binet, que involucra la razón áurea φ. Que una recurrencia de enteros se exprese con irracionales es notable, y su deducción —resolver la ecuación característica x² = x + 1— es el método general para recurrencias lineales homogéneas, análogo al de las ecuaciones diferenciales lineales de la parte 11.

Una precaución numérica: la fórmula de Binet en punto flotante deja de dar el entero exacto para n grande, porque φⁿ crece y la precisión relativa se agota. Para n = 71 el redondeo ya falla. Es un buen recordatorio de que una fórmula cerrada no siempre es preferible a una iteración.

Ejemplo trabajado

Fibonacci por tres caminos.

F(30):
  iterativo:  832040        30 pasos
  Binet:      832040        1 evaluación
  coinciden                            ✓

recursivo ingenuo: 2 692 537 llamadas
  coste O(φⁿ) ≈ O(1.618ⁿ)

Razón entre consecutivos:
  F(31)/F(30) = 1.6180339...
  φ           = 1.6180339...           ✓ converge

Límite de Binet en float64: falla a partir de n ≈ 71

Qué calcula el laboratorio

Recurrencia lineal: iterativo, memoizado y forma cerrada.

python classes/part-04-matematica-discreta-para-computacion/092-recurrencias/lab.py
compmath run 092

Salidas del laboratorio (8)

Muestra de la ejecución real

{
  "recurrencia": "F(n) = F(n-1) + F(n-2)",
  "F(30)_iterativo": 832040,
  "F(30)_binet": 832040,
  "coinciden": true,
  "coste_recursivo_ingenuo": "O(φ^n)",
  "coste_iterativo": "O(n)"
}

Errores comunes

Dónde se usa

Análisis de algoritmos divide y vencerás, programación dinámica, modelos autorregresivos y recurrencias en RNN (clase 313).

Idea rectora de la parte

Permutación cuenta orden; combinación cuenta selección.

Error a evitar

Asumir que un grafo dirigido es acíclico sin verificarlo.

Conexión con IA

Los grafos de cómputo, la búsqueda en árbol y las GNN son estructuras discretas; el conteo sostiene la probabilidad que después usa todo modelo generativo.

Bibliografía de la clase

Archivos de la clase

← 091 Inducción matemática 093 Grafos: vértices y aristas →