JS Fibonacci sequence interpretation

Definition:

Fibonacci sequence – Wikipedia

Formula:

If F0 = 0F_0\ =\ 0F0 = 0 is the first term and F1 = 1F_1\ = 1F1 = 1 is the second term, then starting with the third term and every term thereafter is equal to the sum of the first two terms.

How do you evaluate the Fibonacci sequence in JavaScript?

Implementation in JavaScript:

In chapter 10 of JavaScript Advanced Programming (4th Edition), on the function tail call optimization code (P309), we give an example of calculating the Fibonacci sequence through recursive functions:

function fib(n) {
    if (n < 2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

console.log(fib(0)); / / 0
console.log(fib(1)); / / 1
console.log(fib(2)); / / 1
console.log(fib(3)); / / 2
console.log(fib(4)); / / 3
console.log(fib(5)); / / 5
console.log(fib(6)); / / 8
Copy the code

This function can cause trouble for the browser, for example when calling FIB (1000).

Here is the form of refactoring to satisfy tail-call optimization conditions, using two nested functions, with the outer function as the base frame and the inner function performing recursion:

// The basic framework
function fib(n) {
    return fibImpl(0.1, n);
}

// perform recursion
function fibImpl(a, b, n) {
    if (n === 0) {
        return a;
    }
    return fibImpl(b, a + b, n - 1);
}
Copy the code

Implementation of the iterative loop:

function fib(n) {
    let currNum = 0,
        prevNum = 1,
        arr = [],
        count = 0;

    while(count <= n) {
        arr.push(currNum);
        currNum += prevNum;
        prevNum = currNum - prevNum;
        count++;
    }
    return arr[n];
}

console.log(fib(0)); / / 0
console.log(fib(1)); / / 1
console.log(fib(2)); / / 1
console.log(fib(3)); / / 2
console.log(fib(4)); / / 3
console.log(fib(5)); / / 5
console.log(fib(6)); / / 8

console.log(fib(10)); / / 55
Copy the code

Resolution:

CurrNum computes the value of FnF_nFn in the Fibonacci sequence. PrevNum is the difference between Fn+1F_{n+1}Fn+1 and FnF_nFn. PrevNum is the difference between Fn+1F_{n+1}Fn+1 and FnF_nFn.

The rule is that the value of currNum in the next loop is: current value + difference. As shown by the black arrow on the left.

Therefore, the value of currNum should be updated at the end of each loop, as expressed in JavaScript code:

currNum = currNum + prevNUm;
Copy the code

This can be abbreviated as:

currNum += prevNum;
Copy the code

The prevNum value for the next loop is: the updated currNum value – the current prevNum value.

prevNum = currNum - prevNum;
Copy the code