Programming logic exercise

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

Such a 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 the sequence: 2,3,5.. the successor number of 5 will be 3 + 5 = 8, the successor number of 8 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:

Whenever n is equal to 0 fibo (n) will be equal to 0.

Whenever n equals 1 fibo (n) it will be equal to 1.

2nd Law: a recursive algorithm must change its state and approach its base case.

Our function changes state whenever the value of n changes and approaches the base case, as we repeatedly approach 1 due to the return:

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

(n-1) and (n-2) are responsible for making the state change and indicating the two predecessors of n.

The recursive call of an excerpt of function ex.: fibo(n-1) ends when we arrive at the case where fibo (1) is equal to 1 and fibo(0) is equal to 0.

When all snippets of the function are resolved the final call returns the value of 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. 

Finally

[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 noticed that we divide each part of the problem into smaller parts until these smaller parts reach our base case.

A graphical representation to get more clear:

3rd law: every recursion algorithm must call itself.

This rule is already demonstrated in the example above, after all called fibo(n) = fibo(n-1) + fibo(n-2).

To be clear, another example of a function that calls itself is the Calculate factorial function:

fatorial(x) = x * fatorial(x-1) , but let's put it aside right now and focus on what we have here.

Simple Recursive Function.

Ex.: knowing that the first 10 fibonacci elements 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) = 55

function 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 Displayed

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;
  }
};

In psudocode the equivalent would be

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]
     

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 execute the f(0) = 0 statement, it improves considerably 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 do the steps on paper, so you will have a sense of the steps of recursion.

If there is any error please correct me. I hope I helped somehow.

Hug.