T
Hello, Rafael! To avoid any doubt regarding the subject as a whole I will address from what is the Fibonacci sequence to the functioning of recursive functions and the function you presented ok? Come on!Fibonacci sequence This sequence is governed by the following rule:the next value of the sequence is equal to the sum of its two predecessors.Ex: Considering an excerpt from sequence: 2,3,5.. the successor number of 5 will be 3 + 5 = 8, the number 8 successor would be 8 + 5 = 13 and so on. .Recursion Every recursion algorithm is based on the three laws of recursion:1st Law: every recursive function has a base case.In this function displayed in the image the base cases are:where n is equal to 0 fibo(n) will be equal to 0. where n is equal to 1 fibo(n) will be equal to 1. 2nd Law: A recursive algorithm should change its state and approach its base case.Our function changes state whenever the value of n changes and approaches the base case, because we repeatedly approach 1 due to the return:fibo(n-1) + fibo(n-2)(n-1) and (n-2) are responsible for making the change of state and indicate the two predecessors of n.The recursive call of an excerpt of the function Ex:fibo(n-1) ends when we arrive in the case where fibo(1) is equal to 1 and that fibo(0) is equal to 0.When all sections of the function are solved the final call returns the value of fib.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.
end[estado final: n=3] fibo(3) = (fibo(1) = 1 + fibo(0) = 0) + (fibo(1) = 1)or[estado final: n=3] fibo(3) = (1 + 0) + 1
It is understood that we divide each part of the problem into smaller parts until these smaller parts reach our base case.A graphic representation to be clearer: 3rd Law: Every recursion algorithm should call itself.This rule is already demonstrated in the above example, after all called fibo(n) = fibo(n-1) + fibo(n-2).To make it clearer, another example of a function that calls itself is the factorial calculating function:fatorial(x) = x * fatorial(x-1) , but we're going to put her aside right now and focus on what we have here.Simple Recursive Function.Ex: Knowing that the first 10 elements of fibonacci are:[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
The function I will show below returns:fibonacci(0) = 0, fibonacci(1) = 1, fibonacci(2) = 1, fibonacci(3) = 3 ... fibonacci(9) = 55function fibonacci(n)
{
if (n === 0)
{
return 0
} else
{
if (n === 1)
{
return 1
} else
{
return fibonacci(n-1) + fibonacci(n-2)
}
}
}
In psudocode the equivalent would be: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)
Function Presentedvar 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;
}
};
In psudocode the equivalent would bechame 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]
note that instead of using if n == 0 and if == 1 the function simply considered 1 and returned the two values, making the function more efficient, as this eliminates the need to carry out the instruction f(0) = 0, this considerably improves the efficiency of the algorithm since one of the problems of recursion is the execution of the same calculation several times.I recommend you try to make the steps on paper, so you will have a notion of the steps of recursion.If there is any error please correct me. I hope I helped somehow.Hug.