Fibonacci

La función recursiva de Fibonacci se define como f(0)=0, f(1)=1 y f(n) = f(n-1) + f(n-2) para n≥2. Los primeros téminos de la sucesión son 0, 1, 1, 2, 3, 5, 8, 13, 21,... La espiral de Fibonacci de la Figura representa esta sucesión como arcos de cuadrante inscritos en rectángulos cuyos lados siguen esta sucesión.

Si implementamos un algoritmo que ejecute la función recursiva f(n) = f(n-1) + f(n-2) veremos que no es muy eficiente, pues tendrá un coste exponencial. El recursivo resultante reduce el tamaño del problema en cada llamada mediante substracción, pero no se adapta a los que vimos en el tema anterior que eran de la forma T(n) = a T(n-b) + p(n^k).

La solución exacta de la función recursiva de Fibonacci es f(n) = (Φⁿ - (1-Φ)ⁿ)/5^½, donde Φ = (1+5^½)/2 = 1.618033... (irracional) es la razón áurea. Pero dado que trabajamos con enteros, esa solución puede reducirse a f(n) = [Φⁿ/5^½]. Expresamos [x] como el redondeo del número real x al entero más cercano. Y vemos que abs(1-Φ) < 1 así que abs((1-Φ)ⁿ) será cada vez mucho menor que uno, despreciándose a efectos de cómputo de valores enteros.

Sin embargo esta fórmula puede tener un problema con la precisión del cálculo. En el siguiente ejemplo la ponemos en ejecución para calcular f(72) con la fórmula anterior y con otro algoritmo fibonnaci2() que veremos más abajo:

Se observa que el último dígito no es el mismo, siendo el segundo que finaliza en 4 el valor correcto. Esto tiene que ver con la precisión del formato IEEE754. Los valores que podemos obtener con JavaScript para la razón áurea y para f(72) (sin redondear a entero) son estos:

Vemos que tras redondear f(72) terminará en 5 en lugar del correcto 4. Si utilizamos una calculadora de mayor precisión, como la que viene con Windows, obtenemos estos valores:

Con esa calculadora si obtenemos el valor correcto cuando lo redondeemos al entero más cercano. Si queremos que la función devuelva valores correctos con n grandes y sin calculadora debemos utilizar un algoritmo, como el propio recursivo que define la función f(n) = f(n-1) + f(n-2), que de forma compacta sería como sigue:

function fibonacci1(n){
    if (n<2){
        return n;
    } else {
        return fibonacci1(n-1) + fibonacci1(n-2);
    }
}

Usando la misma estructura de caso trivial, descomposición, llamadas y combinación podemos expresarlo como sigue, donde podemos ubicar un contador de iteraciones en la entrada del recursivo:

function fibonacci1(n){
    numIter++;
    if (n<2){
        //Caso trivial
        return n;
    } else {
        //Descomponemos problema n en 2 subproblemas n-1 y n-2
        let [p1, p2] = [n-1, n-2];
        //1 llamada por cada subproblema
        let s1 = fibonacci1(p1);
        let s2 = fibonacci1(p2);
        //Combinamos soluciones parciales
        return s1+s2;
    }
}

Hemos limitado el máximo valor n≤26, pues con valores grandes la ejecución puede colapsar el navegador. Con ese valor de n=26 ya vemos que el ordenador se queda ejecutando un tiempo perceptible. ¿Tan costoso es de ejecutar este algoritmo? Calculemos el coste. El coste del caso trivial es uno, pues se se realiza un comparativo. En la llamada n≥2 el coste es la suma de las dos llamadas más el coste de la suma de la descomposición del problema y de la combinación de resultados parciales. Suponemos que estas son unitarias por ser operaciones simples y en secuencia con el comparativo resulta un coste unitario, quedando la definición de la recurrencia como sigue:

Usando la expresión modelo de una recurrencia así como las ecuaciones características:

Identificaremos la recurrencia T(n) = T(n-1) + T(n-2) + 1 con este modelo:

Viendo que k=2, b=1 y d=0 (grado del polinomio p(n)) obtenemos la ecuación característica:

Si resolvemos la ecuación de segundo grado obtenemos las soluciones r = (1+5^½)/2 y r = (1-5^½)/2 para la parte homogénea. La otra ecuación tiene por solución r = 1. Una combinación lineal de ellas nos da esta solución:

Indentificamos la razón áurea Φ = (1+5^½)/2 y abreviamos con δ = (1-5^½)/2 quedando como sigue (veáse que δ = 1-Φ pero preferimos identificarlo de forma separada):

Vemos que Φⁿ es la función que domina el orden del coste, puesto que Φ = 1.61803... mayor que 1 y δ = -0.61803... con valor absoluto menor que 1, por lo que a medida que n crece este término será cada vez más insignificante respecto al otro. Así que finalmente podemos suponer que t(n) ∈ O(Φⁿ).

Calculemos las constantes usando los valores triviales T(0) = 1, T(1) = 1. La tercera condición la obtenemos del primer valor de la recurrencia T(2) = T(1) + T(0) + 1 = 3, planteándose estas tres ecuaciones:

Resolviendo obtenemos

{g=(1+sqrt(5))/2,
h=(1-sqrt(5))/2,
x + y + z = 1,
x*g + y*h + z = 1,
x*g^2 + y*h^2 + z = 3}

Con esto el coste exacto en t_n = c₁ Φⁿ + c₂ δⁿ + c₃ es:

con lo que finalmente tenemos el coste:

Usamos el resultado de esta fórmula del coste calculado en el ejemplo, obteniéndose un valor redondeando a entero igual al que resulta de contar las iteraciones con el contador numIter.

Es de notar que si resolvemos la recurrencia de Fibonacci f(n) = f(n-1) + f(n-2) obtenemos la fórmula cerrada f(n) = (1/5^½) (Φⁿ - δⁿ) (con δ=1-Φ), por lo que el coste exacto T(n) parece estar está un orden de potencia por encima de f(n), es decir T(n) = 2 f(n+1)-1.

En la gráfica de la Figura representamos f(n) y T(n) hasta n=16, observándose como T(n) crece por encima de f(n). Vemos por ejemplo que T(16) = 2 f(17)-1 = 2×1597-1 = 3193.

Sin embargo desde el punto de vista del coste asintótico T(n) sigue estando en O(Φⁿ) pues aplicando la regla del límite (resolver en WolframAlpha).

Recursivo Fibonacci con coste lineal

El recursivo f(n) = f(n-1) + f(n-2) es costoso porque se realizan repetidas veces los cálculos. Por ejemplo, para T(5) se calcula 1 vez T(5), 1 vez T(4), 2 veces T(3) y 3 veces T(2). Esto suma 7 operaciones:

T(5) = T(4) + T(3) + 1
    T(4) = T(3) + T(2) + 1
        T(3) = T(2) + T(1) + 1
            T(2) = T(1) + T(0) + 1
        T(2) = T(1) + T(0) + 1
    T(3) = T(2) + T(1) + 1
        T(2) = T(1) + T(0) + 1
    

Hay una forma de reducir esa duplicidad de operaciones y es con el siguiente bucle:

function fibonacci2(n){
    let i = 1, j = 0;
    for (let k=1; k<=n; k++){
        [i, j] = [j, i+j];
    }
    return j;
}

El coste ahora es T(n) ∈ O(n) si consideramos que incrementar una de las dos variables i, j e intercambiarlas tiene coste unitario. Podemos convertir ese iterativo en un recursivo si hacemos una inmersión de resultados en los parámetros de cada llamada tal como vimos en un tema anterior:

function fibonacci3(n, ri=0, rj=1){
    numIter++;
    if (n<1){
        return ri;
    } else if (n<2) {
        return rj;
    } else {
        let p = n-1;
        [ri, rj] = [rj, ri+rj];
        return fibonacci3(p, ri, rj);
    }
}

Pasar resultado parciales a los argumentos no reduce el coste, pero si obtenemos un recursivo final, de tal forma que el resultado se obtiene en la fase de bajada. Esto podría ser una mejora de eficiencia en alguna implementación, tal como explicamos en un tema anterior. De todas formas el coste es T(n) ∈ O(n). Para calcular el coste exacto vemos que los casos triviales tienen coste unitario por los comparativos, mientras que en otro caso vemos un coste unitario combinado en secuencia con los comparativos y las operaciones descomponer problema y operar los parámetros:

La resolución de la recurrencia es idéntica a la del primer apartado del factorial:

Pero ahora las condiciones iniciales son otras, tomamos n=1 cuyo coste es 1 por definición y el primer valor n=2 donde T(2) = T(1)+1 = 1+1 = 2:

Se resuelve con c₁ = 0 y c₂ = 1 por lo que el coste exacto es

Este coste coincide con el contador de iteraciones que hemos puesto en la parte donde se consume coste. Hemos reducido el coste de Fibonacci desde O(Φⁿ) hasta O(n). Pero es que aún hay una forma de reducirlo hasta O(log n) aplicando la técnica denominada divide y vencerás que veremos en un tema siguiente.