0

Estou engatinhado ainda nesse mundo da programação e tentei resolver um problema de lógica sozinho envolvendo a sequência de Fibonacci. Infelizmente eu não obtive sucesso e após procurar na internet, encontrei o mesmo resolvido:

var fibonacci_series = function (n) {
    if (n === 1) 
    {
        return [0, 1];

    } else {

        var s = fibonacci_series(n - 1);
        s.push(s[s.length - 1] + s[s.length - 2]);
        return s;
    }
};

Minhas pergunta é: Por que o if recebe essa condição (n === 1) e retorna um array, e por que essa condição é falsa e cai diretamente no else?

Desde já agradeço a todos que disponibilizarem um tempo para sanar minha dúvida e peço que disponibilizem algum conteúdo que possa agregar valor aos meus estudos.

2
  • Isto responde à sua pergunta? Determinar o n-ésimo termo de Fibonacci com recursividade
    – hkotsubo
    Commented 21/03/2020 às 0:01
  • Basicamente a função está sendo retornada como recursão, ou função recursiva no else, quando seu valor for exatamente e estritamente igual a 1 if(n ===1) você vai retornar 0, 1 que são os dois números da sequencia, e lembrando que os valores estão sendo concatenados na soma adicionando no array. Commented 21/03/2020 às 0:09

1 Resposta 1

7

Olá, Rafael! Para evitar qualquer dúvida em relação ao assunto como um todo vou abordar desde o que é a sequência de Fibonacci até o funcionamento de funções recursivas e a função que você apresentou ok? Vamos lá!

Sequência de Fibonacci

inserir a descrição da imagem aqui

Tal sequência é regida pela seguinte regra:

o próximo valor da sequência é igual a soma do seus dois antecessores.

Ex.: Considerando um trecho da sequencia: 2,3,5.. o número sucessor de 5 será 3 + 5 = 8, o numero sucessor de 8 seria 8 + 5 = 13 e assim por diante...

Recursão

inserir a descrição da imagem aqui

Todo algoritmo de recursão é baseado nas três leis da recursão:

1ª Lei: todo função recursiva possui um caso base.

Nessa função exibida na imagem os casos base são:

sempre que n é igual a 0 fibo(n) será igual a 0. inserir a descrição da imagem aqui

sempre que n é igual a 1 fibo(n) será igual a 1. inserir a descrição da imagem aqui

2ª Lei: Um algoritmo recursivo deve mudar seu estado e se aproximar de seu caso base.

Nossa função muda de estado sempre que o valor de n se altera e se aproxima do caso base, pois repetidas vezes nos aproximamos de 1 devido ao retorno:

fibo(n-1) + fibo(n-2)

(n-1) e (n-2) são responsáveis por fazer a mudança de estado e indicar os dois antecessores de n.

A chamada recursiva de um trecho da função Ex.:fibo(n-1) acaba quando chegarmos no caso em que fibo(1) é igual a 1 e que fibo(0) é igual a 0.

Quando todos os trechos da função estiverem resolvidos a chamada final retorna o valor de fibo.

Ex.: fibo(3) 

[estado inicial: n=3] se n =3, então fibo(3) = fibo(2) + fibo(1).

[estado de transição: n=1] se fibo(1) = 1, então fibo(3) = fibo(2) + 1.

[estado de transição: n=2] se n = 2, então fibo(2) = fibo(1) + fibo(0).

[estado de transição: n=1] fibo(1) = 1 e fibo(0) = 0, então fibo(2) = 1 + 0. 

por fim

[estado final: n=3] fibo(3) = (fibo(1) = 1 + fibo(0) = 0) + (fibo(1) = 1)

ou

[estado final: n=3] fibo(3) = (1 + 0) + 1

Percebe-se que dividimos cada parte do problema em partes menores até que essas partes menores cheguem ao nosso caso base.

Uma representação gráfica pra ficar mais claro:

inserir a descrição da imagem aqui

3ª Lei: Todo algoritmo de recursão deve chamar a si mesmo.

Essa regra já é demonstrada no exemplo acima, afinal chamados fibo(n) = fibo(n-1) + fibo(n-2).

Pra deixar mais claro, um outro exemplo de uma função que chama a sí mesmo é a função calcular fatorial:

fatorial(x) = x * fatorial(x-1) , mas vamos deixá-la de lado neste momento e focar no que temos aqui.

Função Recursiva Simples.

Ex.: Sabendo que os primeiros 10 elementos de fibonacci são:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

A função que mostrarei abaixo retorna:

fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(2) = 1, fibonacci(3) = 3 ... fibonacci(9) = 55

function fibonacci(n)
{
    if (n === 0)
    {
        return 0
    } else
    {
        if (n === 1)
        {
            return 1
        } else
        {
            return fibonacci(n-1) + fibonacci(n-2)
        }
    }
}

Em psudocódigo o equivalente seria:

chame funcao(n)

   se n é igual a 0, entao 
      retorne 0

   se n não é igual a 0, mas é igual a 1, entao 
      retorne 1

   se n não é nem igual a 0 nem igual a 1, então 
      chame funcao(n-2) até que n seja igual a 1 ou a 0
      
      chame funcao(n-1) até que n seja igual a 1 ou a 0

      retorne o resultado de funcao(n-2) + o resultado de funcao(n-1)

Função Apresentada

var fibonacci_series = function (n) {
  if (n===1) 
  {
    return [0, 1];

  } else {

    var s = fibonacci_series(n - 1);
    s.push(s[s.length - 1] + s[s.length - 2]);
    return s;
  }
};

Em psudocódigo o equivalente seria

chame funcao(n)
   se n é igual a 1, entao 

      retorne uma lista [0,1]

   se n não é igual a 1, entao

      insira em s:

         A lista de elementos antecessores ao numero de posição n na sequencia de fibo.
         Ex.: s = [0,1]
      
      acrescente ao final da lista em s:

         A soma do ultimo elemento da lista com o penúltimo elemento da lista.

         Ex.: s[2] = 1 + 0 = 1; s = [0,1,1]

         retorne a lista em s

         Ex.: [0,1,1]
     

observe que ao em vez de usar if n == 0 e if == 1 a função simplesmente considerou 1 e retornou os dois valores, tornando a função mais eficiente, pois isso elimina a necessidade de executar a instrução f(0) = 0, isso melhora consideravelmente a eficiência do algoritmo visto que um dos problemas da recursão é a execução do mesmo cálculo várias vezes.

Recomendo você tentar fazer os passos no papel, assim terá uma noção das etapas da recursão.

Se houver qualquer erro por favor me corrijam. Espero ter ajudado de alguma forma.

Abraço.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .