Como desarrollador, probablemente te hayas encontrado con la tarea de escribir una función para calcular valores en la secuencia de Fibonacci. Este problema clásico aparece a menudo en entrevistas de codificación, y normalmente solicita una implementación recursiva. Sin embargo, en ocasiones los entrevistadores pueden solicitar enfoques específicos. En este artículo, exploraremos las implementaciones de secuencias de Fibonacci más comunes en JavaScript.

¿Qué es la secuencia de Fibonacci?

Primero, refresquemos la memoria. La secuencia de Fibonacci es una serie de números donde cada número es la suma de los dos anteriores. Comienza con 0 y 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55,…

Enfoques de implementación comunes

1. Enfoque recursivo

La solicitud más tradicional es para una implementación recursiva:

function fibonacciRecursive(n) {
  if (n 



Aunque es sencillo, este enfoque no funciona para valores grandes de n. En una MacBook Pro i9 con 16 GB de RAM, calcular el número número 40 de Fibonacci tomó aproximadamente 1,5 segundos:


console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms




Al intentar calcular el número 50, la pestaña de Chrome dejó de responder.

2. Enfoque recursivo con almacenamiento en caché (memorización)

La siguiente variación de esta pregunta es mejorar el rendimiento agregando un mecanismo de almacenamiento en caché a nuestra implementación recursiva:


function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n 



Este enfoque introduce un objeto almacenado en caché con valores iniciales para 0 y 1. Para cualquier número dado, primero verificamos si ya hemos calculado su valor de Fibonacci. Si es así, devolvemos el resultado almacenado en caché en lugar de recalcularlo. De lo contrario, calculamos ese valor y lo almacenamos en caché.

La mejora del rendimiento es significativa (debido a la memoria adicional utilizada, por supuesto). Calcular el número número 40 de Fibonacci tomó ~0,02 ms:


console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms




3. Enfoque iterativo con un bucle for

Otra variación común es implementar la secuencia de Fibonacci usando un bucle for:


function fibonacciWithIteration(n) {
    if (n 



Este enfoque es mucho más rápido que el método recursivo básico (el que no tiene almacenamiento en caché):


console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms




El enfoque iterativo puede manejar valores de entrada muy grandes de manera eficiente:


console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e 292
VM325:23 With iteration: 0.5830078125 ms





  
  
  Bonificación: devolver la secuencia de Fibonacci como una matriz


Los entrevistadores también podrían pedirle que devuelva la secuencia completa de Fibonacci hasta el n-ésimo número como una matriz. Implementemos esto usando enfoques recursivos e iterativos.

Enfoque recursivo


function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1]   arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]




Esta función funciona de la siguiente manera:

Para 0 y 1, devolvemos matrices codificadas.
Para otros casos:

• Obtenemos la secuencia del número anterior y la almacenamos en orden.
• Calculamos el valor actual sumando los dos últimos valores de arr.
• Combinamos arr y currentValue en una nueva matriz y la devolvemos.

Enfoque iterativo

function fibonacciSequenceWithIteration(n) {
  if (n 



Esta función funciona de la siguiente manera:

Si la entrada es 0, devolvemos una matriz con solo el elemento 0.
Para otros casos:

• Inicializamos las variables anterior y siguiente para almacenar los valores anterior y siguiente.
• Creamos arr con valores iniciales [0, 1].
• Iteramos de 2 a n, empujando la suma de prev y next a arr en cada iteración.
• Actualizamos los valores anteriores y siguientes y continuamos con la siguiente iteración.

Conclusión

Si bien este artículo cubre varias implementaciones comunes de secuencias de Fibonacci, no es una lista exhaustiva. Si ha encontrado otras variaciones en las entrevistas o en su trabajo, ¡compártalas en los comentarios!

¡Manténgase actualizado con las últimas noticias sobre desarrollo de software y JavaScript! Únase a mi canal de Telegram para obtener más información y debates: TechSavvy: Frontend & Backend.