Una recurrencia define cada término de una sucesión a partir de términos anteriores. Es la herramienta matemática natural para describir procesos repetitivos, algoritmos recursivos y costos que dependen del tamaño de un problema.
En el tema anterior vimos que una sucesión puede definirse explícitamente, usando una fórmula que depende directamente de n, o recursivamente. Una recurrencia es precisamente una regla recursiva que relaciona un término con uno o más términos anteriores.
Las recurrencias permiten describir un proceso paso a paso. En programación aparecen cuando una función se llama a sí misma, cuando un bucle actualiza un acumulador, cuando un algoritmo divide una entrada o cuando el estado actual depende del anterior.
Para definir una sucesión mediante recurrencia necesitamos una relación de recurrencia y suficientes condiciones iniciales.
Sin la condición inicial, la regla no determina una única sucesión. Por ejemplo, muchas sucesiones cumplen an = an-1 + 3; lo que cambia es el valor desde el cual comienzan.
La relación de recurrencia es la regla que vincula términos. La solución es una sucesión concreta que cumple esa regla y las condiciones iniciales.
| Elemento | Ejemplo |
|---|---|
| Relación | an = an-1 + 3 |
| Condición inicial | a0 = 2 |
| Solución en forma de lista | 2, 5, 8, 11, ... |
| Solución explícita | an = 2 + 3n |
En este tema aprenderemos a reconocer y generar recurrencias. En los próximos veremos métodos sistemáticos para resolver recurrencias sencillas y analizar las que aparecen en algoritmos.
El orden indica cuántos términos anteriores intervienen en la regla. Una recurrencia de primer orden usa solo an-1; una de segundo orden puede usar an-1 y an-2.
| Orden | Regla | Condiciones iniciales necesarias |
|---|---|---|
| 1 | an = 2an-1 | Una, por ejemplo a0. |
| 2 | an = an-1 + an-2 | Dos, por ejemplo a0 y a1. |
| 3 | an = an-1 + an-3 | Tres valores iniciales. |
La cantidad de condiciones iniciales debe ser suficiente para comenzar a aplicar la regla sin ambigüedad.
La forma más simple de recurrencia usa el término inmediatamente anterior. Por ejemplo, an = 2an-1 con a0 = 1 genera potencias de dos.
Esta recurrencia modela procesos que duplican una cantidad en cada paso, como el número de nodos en un árbol binario completo por nivel.
function generarDuplicaciones(inicial, cantidad) {
const terminos = [inicial];
for (let n = 1; n < cantidad; n++) {
terminos.push(2 * terminos[n - 1]);
}
return terminos;
}
console.log(generarDuplicaciones(1, 7)); // [1, 2, 4, 8, 16, 32, 64]La posición n se calcula usando la posición anterior n - 1. El arreglo almacena los términos ya generados para que puedan reutilizarse.
Una recurrencia es lineal cuando cada término anterior aparece multiplicado por constantes y los términos no se multiplican entre sí ni se elevan a potencias. Ejemplos:
La linealidad permite aplicar técnicas algebraicas que estudiaremos más adelante. No significa que la sucesión crezca de manera lineal: una recurrencia lineal puede producir crecimiento exponencial.
Una recurrencia lineal es homogénea cuando no incluye un término independiente. Si se agrega una constante o una función de n, es no homogénea.
| Tipo | Ejemplo | Interpretación |
|---|---|---|
| Homogénea | an = 2an-1 | Solo depende del valor anterior. |
| No homogénea | an = 2an-1 + 1 | Duplica y agrega un costo fijo. |
| No lineal | an = (an-1)² | El término anterior se eleva al cuadrado. |
Los costos de algoritmos suelen ser no homogéneos porque, además de resolver subproblemas, realizan trabajo adicional como comparar, dividir o combinar datos.
Fibonacci es una recurrencia lineal homogénea de segundo orden. Cada término depende de los dos anteriores:
Para calcular F2 necesitamos dos condiciones iniciales. Para calcular cada término posterior necesitamos mantener o recuperar los dos valores previos.
function fibonacci(n) {
if (!Number.isInteger(n) || n < 0) {
throw new Error("n debe ser un entero no negativo");
}
let anterior = 0;
let actual = 1;
for (let i = 0; i < n; i++) {
[anterior, actual] = [actual, anterior + actual];
}
return anterior;
}
console.log(fibonacci(0)); // 0
console.log(fibonacci(10)); // 55La implementación no almacena todos los términos porque la regla requiere solamente los dos más recientes. Esta es una optimización de memoria basada en conocer la estructura de la recurrencia.
Una recurrencia de la forma an = an-1 + g(n) representa un acumulador. Cada paso conserva el valor anterior y agrega una nueva contribución.
Este patrón aparece en sumas acumuladas, conteo de operaciones y procesamiento de datos secuenciales.
function sumasAcumuladas(n) {
const terminos = [0];
for (let i = 1; i <= n; i++) {
terminos.push(terminos[i - 1] + i);
}
return terminos;
}
console.log(sumasAcumuladas(5)); // [0, 1, 3, 6, 10, 15]Una recurrencia puede describir cómo cambia el estado de un sistema en pasos discretos. Si un saldo recibe un interés mensual fijo, cada valor depende del saldo del mes anterior. Si una simulación actualiza una posición, el nuevo estado depende del anterior y de la velocidad.
La elección de una recurrencia obliga a explicitar qué información del pasado se necesita conservar para calcular el futuro.
function saldoPorMeses(saldoInicial, tasaMensual, meses) {
const saldos = [saldoInicial];
for (let mes = 1; mes <= meses; mes++) {
saldos.push(saldos[mes - 1] * (1 + tasaMensual));
}
return saldos;
}
console.log(saldoPorMeses(1000, 0.02, 3));
// [1000, 1020, 1040.4, 1061.208]El ejemplo usa números decimales para simplificar la explicación. En sistemas financieros reales deben definirse reglas precisas de redondeo y unidades monetarias.
Los algoritmos que dividen un problema en subproblemas se describen a menudo mediante recurrencias. Si un algoritmo resuelve dos subproblemas de tamaño n/2 y luego realiza n operaciones para combinar resultados, su costo puede expresarse como:
La primera parte cuenta el costo de las llamadas recursivas; el término + n cuenta el trabajo local. Más adelante resolveremos este tipo de expresiones para estimar la complejidad de algoritmos como merge sort.
Una recurrencia es una relación matemática entre términos de una sucesión. La recursión es una técnica de programación en la que una función se llama a sí misma. Están relacionadas, pero no son lo mismo.
| Concepto | Pregunta que responde | Ejemplo |
|---|---|---|
| Recurrencia | ¿Cómo se relaciona T(n) con términos previos? | T(n) = T(n-1) + 1 |
| Función recursiva | ¿Cómo se implementa un cálculo por llamadas? | factorial(n) llama a factorial(n-1) |
| Algoritmo iterativo | ¿Cómo se actualiza un estado en un bucle? | suma += i |
Una función recursiva suele generar una recurrencia de costo. Un algoritmo iterativo también puede describirse con una recurrencia, aunque no se llame a sí mismo.
Las recurrencias expresan cómo un proceso avanza utilizando información de pasos anteriores. Son el puente entre sucesiones, programas iterativos, funciones recursivas y análisis de complejidad.
En el próximo tema estudiaremos con detalle las relaciones de recurrencia de primer orden y sus formas más frecuentes.