Fibonacci sin recursión lenta: de LAMBDA exponencial a fórmula instantánea

Un ingeniero industrial del grupo implementa Fibonacci con LAMBDA recursiva (Fibonacci(n-1)+Fibonacci(n-2)), pero a partir de n=35 la fórmula tarda más de un minuto. El motivo: cada llamada genera dos sub-llamadas, creciendo exponencialmente (2^35 = ~34 mil millones de evaluaciones).

La comunidad propone dos enfoques radicalmente diferentes:

Fibonacci iterativo con APILARV + TOMAR (Héctor): construye la secuencia paso a paso, apilando cada nuevo valor calculado a partir de los dos últimos:

``
=LET(
F; LAMBDA(F; arr; n;
SI(FILAS(arr) >= n; arr;
F(F; APILARV(arr; SUMA(TOMAR(arr; -2))); n)
)
);
INDICE(F(F; {1; 1}; A1); A1)
)
`

Complejidad lineal O(n) en vez de exponencial.

Fórmula cerrada de Binet (Leo): la solución matemática directa. No necesita recursión ni iteración — calcula el resultado en una sola evaluación:

`
=LET(
n; 40;
k; 5^0,5;
(((1 + k) / 2)^n - ((1 - k) / 2)^n) / k
)
`

Donde k = √5 y la fórmula usa la proporción áurea (1+√5)/2. Resultado instantáneo para cualquier n.

La serie completa con REDUCE: esos mismos días salió en la comunidad otra variante del reto, generar los N primeros números en una sola celda. Parte de {1;1} y en cada vuelta apila con APILARV la suma de los dos últimos valores; con n=40 devuelve los 40 primeros términos, hasta 102.334.155. Es el patrón de acumulación que no se puede hacer con MAP ni BYROW`, porque cada paso depende del anterior. La fórmula completa está en la explicación paso a paso.

El autor confirma que la fórmula de Leo es "impecable: exacta y super rápida". Un caso que ilustra bien cómo pensar en el algoritmo (iterativo vs recursivo vs analítico) es más importante que optimizar la fórmula.

El problema: Fibonacci que tarda un minuto

Un ingeniero industrial del grupo implementó la sucesión de Fibonacci con una LAMBDA recursiva clásica: cada término es la suma de los dos anteriores. Elegante sobre el papel, pero a partir de n=35 la fórmula tardaba más de un minuto en calcular. ¿Por qué?

Porque esa recursión es exponencial. Cada llamada genera dos sub-llamadas, que a su vez generan dos cada una... Para n=35 son del orden de miles de millones de evaluaciones, la mayoría repetidas. La comunidad respondió con dos enfoques que atacan el problema desde ángulos opuestos.

Enfoque 1: iterativo con APILARV + TOMAR

Héctor cambió la recursión que se ramifica por una que construye la secuencia paso a paso, apilando cada nuevo término a partir de los dos últimos:

=LET(
    F; LAMBDA(F; arr; n;
        SI(FILAS(arr) >= n; arr;
            F(F; APILARV(arr; SUMA(TOMAR(arr; -2))); n)
        )
    );
    INDICE(F(F; {1; 1}; A1); A1)
)

TOMAR(arr; -2) coge los dos últimos valores, SUMA los suma y APILARV añade el resultado a la lista. La recursión avanza una sola vez por término, así que el coste es lineal en lugar de exponencial. Para n=35 pasa de un minuto a instantáneo.

Enfoque 2: la fórmula cerrada de Binet

Leo fue directo a las matemáticas. Existe una fórmula cerrada para Fibonacci —la fórmula de Binet— que da el término n-ésimo sin recursión ni iteración, en una única evaluación:

=LET(
    n; A1;
    k; 5^0,5;
    (((1 + k) / 2)^n - ((1 - k) / 2)^n) / k
)

Donde k es la raíz de 5 y (1+k)/2 es la famosa proporción áurea. El resultado es inmediato para cualquier n, porque no recorre nada: simplemente evalúa una expresión. El autor del caso la calificó de "impecable: exacta y súper rápida".

Enfoque 3: la serie entera con REDUCE

Esos mismos días salió en la comunidad otra variante del reto: no calcular un término, sino generar los N primeros números de la serie en una sola celda, sin recursión, con REDUCE como motor:

=LAMBDA(n;
    LET(
        secuencia; REDUCE(
            {1;1};
            SECUENCIA(SI(2>=n;n;n-2));
            LAMBDA(arr;i;
                LET(
                    ultimo; INDICE(arr;FILAS(arr));
                    penultimo; INDICE(arr;FILAS(arr)-1);
                    nuevo; ultimo + penultimo;
                    APILARV(arr;nuevo)
                )
            )
        );
        TOMAR(secuencia;n)
    )
)(40)

Se parte de {1;1}, los dos primeros términos. SECUENCIA marca cuántas vueltas faltan y, en cada una, INDICE con FILAS lee el último y el penúltimo valor del acumulador, los suma y APILARV devuelve la serie con un elemento más. Al final, TOMAR recorta al tamaño pedido. Con 40, la serie llega hasta 102.334.155. Si solo quieres el término n, cambia el TOMAR final por INDICE(secuencia;n).

Es el mismo planteamiento lineal que el de Héctor, pero sin que la función se llame a sí misma. Y enseña por qué el motor tiene que ser REDUCE: MAP y BYROW tratan cada elemento por separado, mientras que REDUCE arrastra un acumulador de una vuelta a la siguiente, que es justo lo que pide un cálculo en el que cada paso depende del anterior.

Iterativo vs analítico: qué elegir

Las dos soluciones son mucho mejores que la recursión ramificada, pero no son idénticas. La iterativa te da toda la secuencia hasta n, lo cual es útil si necesitas la lista completa, y es exacta con enteros para cualquier tamaño. La de Binet es la más rápida y compacta, ideal cuando solo quieres el término n; su único matiz es que, al trabajar con potencias de números irracionales, en valores muy grandes puede aparecer un pequeñísimo error de redondeo de coma flotante.

Funciones clave

  • LAMBDA recursiva: se llama a sí misma; hay que controlar cómo crece el número de llamadas.
  • iteración con APILARV: construye la secuencia en una pasada lineal.
  • TOMAR: extrae los últimos elementos ya calculados.
  • SUMA y potencia (^): la base de la fórmula de Binet.

Conclusión

El caso ilustra una lección que va mucho más allá de Fibonacci: el algoritmo importa más que la fórmula. La misma función, escrita como recursión exponencial, tarda un minuto; pensada como iteración lineal o como fórmula analítica, es instantánea. Antes de optimizar celdas, conviene preguntarse si el enfoque de fondo es el correcto. Reflexiones así surgen cada semana en la comunidad de InflueXcel.

Más casos con estas funciones

Más contenido de Excel en InflueXcel