​

Como resolver?

O ponto chave aqui é a realização de somas consecutivas de números. Uma das formas que podemos utilizar para conseguir isso é utilizando recursão para ir somando os números anteriores até chegar em 1, que seria o primeiro valor da sequência.

Resolução

Começamos a resolução pensando, mais uma vez, no nosso caso base para a função recursiva. Para a sequência de Fibonnaci temos dois casos base diferentes, que é quando o número passado é 0 e quando o número passado é 1. Caso seja 0, deve retornar também 0, e caso seja 1, retorna 1.

function fibonacci(num) {  if (num === 0) return 0
  if (num === 1) return 1
}

Agora precisamos calcular os outros valores. Como os números da sequência de Fibonnaci são formados a partir da soma dos seus dois anteriores, tudo que precisamos fazer é chamar recursivamente a própria função passando o número anterior (n - 1) e o anterior ao anterior (n - 2). Com isso, a função chamará ela mesma até que chegue aos valores 1 e 0, que retornarão a soma 1 e então irão resolver as chamadas recursivas uma a uma.

function fibonacci(num) {
  if (num === 0) {
		return 0
	]

  if (num === 1) {
		return 1
	}

	return fibonacci(num - 1) + fibonacci(num - 2)
}

Nossa função está funcionando, no entanto se tentar executar números um pouco maiores como 40 ou 50 logo veremos que sua execução está lenta, então ainda não terminamos. Isso está acontecendo pois a cada chamada da função fibonacci, duas novas funções fibonnaci estão sendo chamadas, fazendo com que isso aumente muito o número de funções em valores mais altos. Além disso, a função acaba sendo chamada mais de uma vez para um mesmo valor, afinal em um momento é chamada a função fibonacci(num - 2), mas antes disso ela já foi chamada, porque ao chamar fibonacci(num - 1) dentro dela também será chamada fibonnaci(num - 1) que será equivalente a fibonnaci(num - 2) do nível anterior.

Nesse caso, uma forma que podemos utilizar para resolver esse problema é memorizando o valor dos resultados das funções executadas, assim, se aquele valor já tiver sido calculado em um momento, quando ele for chamado novamente o resultado já estará disponível. Podemos fazer isso através de um objeto, armazenando o valor em uma propriedade com o número equivalente. Dentro da nossa função podemos começar com uma verificação usando os colchetes para referenciar uma propriedade do objeto. Se o objeto já possuir uma propriedade naquela posição com um valor numérico isso significa que aquela posição já foi calculada antes, então basta retornar esse valor sem precisar chamar a função recursivamente. E antes de retornar o resultado da função usamos mais uma vez a sintaxe de colchetes para armazenar o resultado dentro do objeto na posição do número.

let fibonacciCache = {}

function fibonacci(num) {
  if (typeof fibonacciCache[num] === 'number') {
    return fibonacciCache[num]
  }

  let result = 0

  if (num === 1) {
    result = 1
  } else if (num >= 2) {
    result = fibonacci(num - 1) + fibonacci(num - 2)
	}
  
  fibonacciCache[num] = result

  return result
}

Agora vamos ver que nossa função já executa muito mais rápido. Porém ainda falta um detalhe, em números muito grandes o javascript não é capaz de calcular um resultado preciso. Como a sequência de Fibonnaci é composta somente de inteiros podemos mais uma vez utilizar o tipo BigInt para lidar com números muito grandes. Só precisamos garantir que o número que recebemos seja convertido para BigInt no começo da função, pois não podemos misturar numbers e bigints nas nossas operações.

let fibonacciCache = {}

function fibonacci(num) {
  const big = BigInt(num)

  if (typeof fibonacciCache[big] === 'bigint') {
    return fibonacciCache[big]
  }

  let result = 0n

  if (big === 1n) {
    result = 1n
  } else if (big >= 2n) {
    result = fibonacci(big - 1n) + fibonacci(big - 2n)
	}
  
  fibonacciCache[big] = result

  return result
}