Resolver una recurrencia consiste en obtener una fórmula explícita para su término n. Esa fórmula permite calcular valores lejanos, estudiar el crecimiento y analizar algoritmos sin expandir cada paso uno por uno.
Una relación de recurrencia describe cómo obtener un término a partir de otros. Sin embargo, si queremos conocer a1000, puede ser incómodo calcular los 999 términos intermedios. Una solución explícita expresa an directamente en función de n.
En este tema resolveremos recurrencias elementales usando expansión o sustitución repetida, reconocimiento de sumas y productos, y verificación final. Son técnicas fundamentales para entender el comportamiento de secuencias y costos de algoritmos.
Una fórmula propuesta solo es solución si cumple tanto la condición inicial como la relación de recurrencia. Comprobar ambas condiciones es parte obligatoria de la resolución.
El método de expansión reemplaza repetidamente un término por la regla de recurrencia hasta llegar al término inicial. Al observar el patrón, podemos expresar el resultado en función de n.
La expansión no debe detenerse solo porque vemos algunos términos. Debemos indicar cuántas veces se aplicó la regla y por qué el patrón alcanza el índice inicial.
Consideremos la forma general an = an-1 + d, con a0 = c. Al expandir n veces se obtiene:
La sucesión es aritmética. El término inicial aparece una vez y el incremento d aparece una vez por cada paso desde 0 hasta n, es decir, n veces.
Para verificar an = 7 - 2n, comprobamos primero el caso inicial y luego la regla.
function terminoRecursivoAditivo(inicial, diferencia, n) {
let valor = inicial;
for (let i = 1; i <= n; i++) {
valor += diferencia;
}
return valor;
}
function terminoExplicitoAditivo(inicial, diferencia, n) {
return inicial + n * diferencia;
}
console.log(terminoRecursivoAditivo(7, -2, 5)); // -3
console.log(terminoExplicitoAditivo(7, -2, 5)); // -3La primera función aplica la relación paso a paso; la segunda usa la solución explícita. Ambas deben coincidir para los valores válidos.
Para an = r an-1 con a0 = c, la expansión produce un producto de r repetido n veces.
La sucesión es geométrica. Si r = 2, cada paso duplica el valor y la fórmula contiene una potencia de dos.
La solución se verifica sustituyendo: 2an-1 = 2(5 · 2n-1) = 5 · 2n, que coincide con la fórmula propuesta.
function terminoRecursivoMultiplicativo(inicial, factor, n) {
let valor = inicial;
for (let i = 1; i <= n; i++) {
valor *= factor;
}
return valor;
}
function terminoExplicitoMultiplicativo(inicial, factor, n) {
return inicial * factor ** n;
}
console.log(terminoRecursivoMultiplicativo(5, 2, 4)); // 80
console.log(terminoExplicitoMultiplicativo(5, 2, 4)); // 80Consideremos an = an-1 + n, con a0 = 0. Al expandir, aparecen todos los sumandos desde 1 hasta n:
Resolver una recurrencia puede reducirse a reconocer una suma conocida. La inducción matemática permite demostrar la fórmula de esa suma.
Una suma telescópica tiene términos que se cancelan al sumarse. Por ejemplo, si an = an-1 + 1/[n(n + 1)] con a0 = 0, podemos usar:
Este método es útil cuando la diferencia entre términos puede descomponerse en dos partes consecutivas que se cancelan.
La recurrencia an = r an-1 + b combina multiplicación y suma. Si r ≠ 1, la expansión produce una suma geométrica:
Esta fórmula será útil para muchos modelos. Cuando r = 1, la recurrencia se convierte en la forma aditiva an = an-1 + b.
Consideremos a0 = 1 y an = 2an-1 + 1. Aplicando la fórmula anterior:
Podemos verificar sustituyendo la fórmula en la recurrencia: 2(2n - 1) + 1 = 2n+1 - 1.
function recurrenciaAfin(n) {
let valor = 1;
for (let i = 1; i <= n; i++) {
valor = 2 * valor + 1;
}
return valor;
}
function formulaAfin(n) {
return 2 ** (n + 1) - 1;
}
console.log(recurrenciaAfin(4)); // 31
console.log(formulaAfin(4)); // 31Una vez que proponemos una fórmula, podemos comprobarla por sustitución. El procedimiento tiene dos pasos:
Para mayor rigor, la verificación general puede formalizarse mediante inducción matemática. El método de sustitución sirve para detectar errores algebraicos y confirmar que una expresión candidata es coherente con la recurrencia.
El tiempo de un algoritmo puede definirse mediante recurrencias. Si una función hace una operación local y luego llama a una versión con tamaño n - 1, podemos tener:
La solución permite pasar de una descripción de llamadas a una conclusión de complejidad. En temas posteriores aplicaremos este razonamiento a algoritmos recursivos más variados.
La expansión y el reconocimiento de sumas resuelven muchas recurrencias simples, pero no todas. Fibonacci, las recurrencias de orden mayor y las recurrencias que dividen el tamaño del problema requieren herramientas adicionales.
| Recurrencia | Técnica elemental | Comentario |
|---|---|---|
| an = an-1 + d | Expansión | Produce una suma constante. |
| an = ran-1 | Expansión | Produce una potencia. |
| an = an-1 + n | Reconocer suma | Produce suma de naturales. |
| Fn = Fn-1 + Fn-2 | No basta lo anterior | Requiere métodos de segundo orden. |
Las fórmulas explícitas hacen visible el crecimiento de una sucesión y preparan el análisis de algoritmos. En el próximo tema relacionaremos directamente los algoritmos recursivos con las recurrencias que describen su costo.