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
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
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.
sempre que n é igual a 1 fibo(n) será igual a 1.
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:
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.