Una relación de recurrencia de primer orden calcula cada término a partir del inmediatamente anterior. Estas reglas simples modelan acumulaciones, crecimiento porcentual, procesos iterativos y numerosos costos de algoritmos.
Una recurrencia es de primer orden cuando el término an depende de an-1, y no de términos más antiguos. Para comenzar a generar la sucesión basta conocer un único valor inicial.
La regla puede sumar, multiplicar o transformar de otra manera el término anterior. Aunque la estructura es sencilla, el comportamiento resultante puede ser lineal, exponencial, convergente, alternante o mucho más complejo.
Por ejemplo, an = an-1 + 5 con a0 = 2 es de primer orden porque solo utiliza el término anterior. La sucesión resultante es 2, 7, 12, 17, ...
La misma relación puede generar muchas sucesiones diferentes. La condición inicial selecciona una de ellas.
| Relación | Valor inicial | Sucesión |
|---|---|---|
| an = an-1 + 3 | a0 = 0 | 0, 3, 6, 9, ... |
| an = an-1 + 3 | a0 = 5 | 5, 8, 11, 14, ... |
| an = an-1 + 3 | a0 = -2 | -2, 1, 4, 7, ... |
En un programa, el valor inicial puede representar el estado antes del primer paso: saldo inicial, cantidad de elementos, posición, contador o costo base.
Una recurrencia aditiva agrega una cantidad al término anterior. La forma más simple es an = an-1 + d, donde d es constante.
Esta es una progresión aritmética. Su crecimiento es lineal respecto de n porque cada paso incorpora la misma cantidad.
function generarAditiva(inicial, incremento, cantidad) {
const terminos = [inicial];
for (let n = 1; n < cantidad; n++) {
terminos.push(terminos[n - 1] + incremento);
}
return terminos;
}
console.log(generarAditiva(10, 4, 6)); // [10, 14, 18, 22, 26, 30]El arreglo sirve como memoria de los términos previos. En este caso podríamos conservar solo el último valor, ya que la relación no necesita los anteriores.
Una recurrencia multiplicativa tiene la forma an = r an-1, donde r es una constante. Cada paso multiplica por el mismo factor.
Si |r| > 1, el valor crece en magnitud de forma exponencial. Si 0 < r < 1, decrece hacia cero en el modelo de números reales. Si r es negativo, los signos alternan.
function generarMultiplicativa(inicial, factor, cantidad) {
const terminos = [inicial];
for (let n = 1; n < cantidad; n++) {
terminos.push(terminos[n - 1] * factor);
}
return terminos;
}
console.log(generarMultiplicativa(2, 3, 5)); // [2, 6, 18, 54, 162]El patrón aparece en interés compuesto, reproducción idealizada de poblaciones, ramas de un árbol y algoritmos que duplican la cantidad de trabajo en cada nivel.
Una recurrencia lineal de primer orden muy frecuente tiene la forma an = r an-1 + b. Combina una multiplicación con una suma fija.
Esta forma describe procesos que escalan un estado y agregan trabajo local. En el ejemplo, los términos son uno menos que potencias de dos: an = 2n+1 - 1.
function generarAfin(inicial, factor, constante, cantidad) {
const terminos = [inicial];
for (let n = 1; n < cantidad; n++) {
terminos.push(factor * terminos[n - 1] + constante);
}
return terminos;
}
console.log(generarAfin(1, 2, 1, 6)); // [1, 3, 7, 15, 31, 63]El orden y la linealidad son conceptos distintos. Una relación puede ser de primer orden y no lineal si usa solo an-1, pero lo eleva al cuadrado, lo multiplica por sí mismo o aplica una función no lineal.
Estas sucesiones pueden crecer muy rápido y no suelen resolverse con las mismas técnicas elementales que las recurrencias lineales.
La cantidad agregada o el factor pueden depender del índice. Por ejemplo, an = an-1 + n genera las sumas acumuladas de los naturales.
A diferencia de una recurrencia aditiva con incremento constante, aquí el cambio entre términos aumenta: primero se suma 1, luego 2, luego 3 y así sucesivamente.
function sumasAcumuladas(cantidad) {
const terminos = [0];
for (let n = 1; n <= cantidad; n++) {
terminos.push(terminos[n - 1] + n);
}
return terminos;
}
console.log(sumasAcumuladas(6)); // [0, 1, 3, 6, 10, 15, 21]Este patrón modela el trabajo de un algoritmo con un bucle anidado donde, en la iteración n, se realizan n operaciones adicionales.
Las recurrencias de primer orden son modelos naturales de sistemas donde el estado futuro depende solo del estado actual. Esta propiedad se conoce en muchos contextos como sin memoria adicional o propiedad de Markov, aunque el modelo exacto puede incluir otras variables.
| Situación | Modelo de primer orden |
|---|---|
| Saldo con interés | Sn = 1,02Sn-1 |
| Temperatura suavizada | Tn = 0,8Tn-1 + 0,2Mn |
| Contador de eventos | Cn = Cn-1 + eventon |
| Posición por pasos | Pn = Pn-1 + desplazamienton |
El suavizado exponencial combina el valor anterior con una nueva medición. El factor α determina qué peso recibe la medición reciente.
function suavizar(mediciones, alpha) {
const valores = [mediciones[0]];
for (let n = 1; n < mediciones.length; n++) {
valores.push(alpha * mediciones[n] + (1 - alpha) * valores[n - 1]);
}
return valores.map(valor => Number(valor.toFixed(2)));
}
console.log(suavizar([20, 30, 22, 28], 0.5)); // [20, 25, 23.5, 25.75]Esta recurrencia es de primer orden porque cada valor suavizado necesita únicamente el valor suavizado anterior y la medición actual.
Un bucle que actualiza una variable puede describirse con una recurrencia. Identificarla ayuda a predecir valores y a demostrar invariantes.
La iteración con índice i corresponde al paso n de la sucesión. Esta traducción conecta el código con la fórmula que describe su estado.
Generar términos uno por uno es útil, pero a menudo queremos una fórmula para an. Para una recurrencia aditiva an = an-1 + d, al expandir varios pasos observamos:
Este procedimiento de expansión, junto con otros métodos, será el centro del próximo tema sobre resolución de recurrencias sencillas.
Las relaciones de primer orden ofrecen un modelo compacto para procesos que avanzan usando solo su estado más reciente. Reconocer sus tipos permite anticipar el crecimiento, generar términos y conectar modelos matemáticos con implementaciones iterativas.
En el próximo tema aprenderemos a resolver recurrencias sencillas y obtener fórmulas explícitas para sus términos.