How does it work (an algorithm using recursion to calculate the Fibonacci number)?

Question

JavaScript

When you try to understand, your head just explodes... Why isn't the result 13? (After all, n (8) - 1 = 7 and n (8) - 2 = 6). Where is all this saved while the Fibonacci number is being calculated? And why do we need these (n - 1) with (n - 2) in the function?

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

var result = getFibonachi(8);
console.log(result);

Answer 1

Fibonacci numbers are a sequence starting from 0 and 1, where each next is equal to the sum of the previous two.
The third is equal The 0 + 1 = 1 // итого первые три ряда: 0 1 1
fourth is the sum of the last two units = 2 // 0 1 1 2
The fifth is 1 + 2 = 3 // 0 1 1 2 3
And so on. Here is the beginning of the series:

значение:         0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
порядковый номер: 0  1  2  3  4  5  6   7   8   9  10  11  12

The eighth, if counted from 0, is equal to 21. Not a value is passed
as a parameter to the function , but the ordinal number of the element of the Fibonacci series, and the function must return the value. To calculate the next value, you need to know the previous two. From here and Since any element of the series is considered the same, only one function is written. It is immediately ready to give an answer for the first two elements if n = 0 or 1. In other cases, it will have to call itself. The JavaScript engine will take care of storing the intermediate values ​​and the chain of who called whom and with what parameter. getFibonachi()

Answer 2

During code execution, an auxiliary structure called a stack is created in RAM. It works on the LIFO principle - last in, first out. When you call a function, some of its data is added to the stack - arguments, memory location, return address (in general, this data is implementation dependent).
That is, when you called getFibonachi(8) a record of that call was created on the stack. In this case, n == 8. That is, we get into else and call getFibonachi(7). The stack now has an entry for two functions. Etc. As long as n == 1. Then the function will return 1. This last function is removed from the stack. That is, at this stage, the stack contains the following functions:
getFibonachi(2)
getFibonachi(3)
getFibonachi(4)
getFibonachi(5)
getFibonachi(6)
getFibonachi(7)
getFibonachi(8)
We return to the execution of the function called with argument 2. At this point, we calculated the getFibonachi(1) function (it was successfully evaluated and returned 1) and now we move on to the second term. getFibonachi(0) (because n==2). It returns 0. We can now evaluate the getFibonachi(2) function because we have already received values ​​from the two functions that were called in the else block. getFibonachi(2) will return 1 (1+0=1) and pop off the stack. Now it looks like this:
getFibonachi(3)
getFibonachi(4)
getFibonachi(5)
getFibonachi(6)
getFibonachi(7)
getFibonachi(8) We
continue the function from the top of the stack. And so on until all functions return values)) Google for more details:function call stack . A little crooked, but how could.
You can use the js debugger in the browser. To visualize the work of the stack.

Answer 3

Everything from the definition of the Fibonacci series - the next element of the series is equal to the sum of the two previous elements.
And everything goes on the stack. Learn how the function call stack works in Javascript.