Como desenvolvedor, você provavelmente já se deparou com a tarefa de escrever uma função para calcular valores na sequência de Fibonacci. Este problema clássico aparece frequentemente em entrevistas de codificação, normalmente solicitando uma implementação recursiva. No entanto, os entrevistadores podem, por vezes, solicitar abordagens específicas. Neste artigo, exploraremos as implementações mais comuns da sequência de Fibonacci em JavaScript.

O que é a sequência de Fibonacci?

Primeiro, vamos refrescar nossa memória. A sequência de Fibonacci é uma série de números onde cada número é a soma dos dois anteriores. Começa com 0 e 1:

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

Abordagens comuns de implementação

1. Abordagem recursiva

A solicitação mais tradicional é para uma implementação recursiva:

function fibonacciRecursive(n) {
  if (n 



Embora simples, essa abordagem não tem bom desempenho para valores grandes de n. Em um MacBook Pro i9 com 16 GB de RAM, o cálculo do 40º número de Fibonacci demorou cerca de 1,5 segundos:


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

VM379:3 Recursive: 1521.569091796875 ms




A tentativa de calcular o 50º número fez com que a guia do Chrome parasse de responder.

2. Abordagem recursiva com cache (memoização)

A próxima variação desta questão é melhorar o desempenho adicionando um mecanismo de cache à nossa implementação recursiva:


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



Esta abordagem introduz um objeto em cache com valores iniciais para 0 e 1. Para qualquer número, primeiro verificamos se já calculamos seu valor de Fibonacci. Nesse caso, retornamos o resultado armazenado em cache em vez de recalculá-lo. Caso contrário, calculamos esse valor e o armazenamos em cache.

A melhoria de desempenho é significativa (devido à memória adicional usada, é claro). O cálculo do 40º número de Fibonacci levou aproximadamente 0,02 ms:


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

VM382:3 Recursive, with caching: 0.01806640625 ms




3. Abordagem iterativa com um loop for

Outra variação comum é implementar a sequência de Fibonacci usando um loop for:


function fibonacciWithIteration(n) {
    if (n 



Essa abordagem é muito mais rápida que o método recursivo básico (aquele sem cache):


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

VM44:22 With iteration: 0.10107421875 ms




A abordagem iterativa pode lidar com valores de entrada muito grandes de forma 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





  
  
  Bônus: retornando a sequência de Fibonacci como um array


Os entrevistadores também podem pedir que você retorne toda a sequência de Fibonacci até o n-ésimo número como uma matriz. Vamos implementar isso usando abordagens recursivas e iterativas.

Abordagem recursiva


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 função funciona da seguinte maneira:

Para 0 e 1, retornamos matrizes codificadas.
Para outros casos:

• Obtemos a sequência do número anterior e a armazenamos em arr.
• Calculamos currentValue somando os dois últimos valores de arr.
• Combinamos arr e currentValue em um novo array e o retornamos.

Abordagem iterativa

function fibonacciSequenceWithIteration(n) {
  if (n 



Esta função funciona da seguinte maneira:

Se a entrada for 0, retornamos um array com apenas o elemento 0.
Para outros casos:

• Inicializamos as variáveis ​​anteriores e próximas para armazenar os valores anteriores e seguintes.
• Criamos arr com valores iniciais [0, 1].
• Nós iteramos de 2 a n, empurrando a soma de anterior e próximo para arr em cada iteração.
• Atualizamos os valores anteriores e seguintes e continuamos para a próxima iteração.

Conclusão

Embora este artigo cubra várias implementações comuns de sequência de Fibonacci, não é uma lista exaustiva. Se você encontrou outras variações em entrevistas ou em seu trabalho, compartilhe-as nos comentários!

Fique atualizado com as últimas notícias sobre JavaScript e desenvolvimento de software! Junte-se ao meu canal Telegram para mais insights e discussões: TechSavvy: Frontend & Backend.