1. What are Fibonacci numbers

The Fibonacci sequence, also known as the Golden section sequence, was introduced by mathematician Leonardoda Fibonacci using rabbit breeding as an example. It refers to a sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34… Mathematically, the Fibonacci sequence is defined recursively as follows: F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) (n ≥ 3, n ∈ N*)

2. Realization of Fibonacci sequence

2.1 the recursive

The first thing that comes to mind when you look at this problem is recursion

let fib = function(n) {
    if(n <= 2) {
        return1}return fib(n-2) + fib(n-1)
}
Copy the code

2.1.1 Recursive optimization

If you want to retrieve an item in a sequence, the above method is sufficient, but if you need to retrieve a sequence, you can easily find repeated calls to the above method, so you can cache the previous data in an array

letMemorize = [1, 1]let fib = function(n) {
    redo++
    if(! memorize[n-1]) { memorize[n-1] = fib(n-1) + fib(n-2) }return memorize[n-1]
}
Copy the code

2.2 Tail recursive invocation

Tail Call is an important concept of functional programming. It is very simple in itself. The last step of a function is to Call another function.

let fib = function(n, prev=1, next=1) {
    if(n <= 2) {
        return next
    }
    return fib(n-1, next, prev + next)
}
Copy the code

2.3 recursive

In the recursive algorithm above, when we get the value of a certain item, we go from back to front. Now we go from front to back, which is recursion. Since the first two terms add up to the third term, the expression is res[I -2] + res[I -1] = res[I]

2.3.1 for loop

let fib = function(n) {
    if(n<=2) {
        return1}let sum = 0
    let prev = 1
    let next = 1
    for(leti=3; i<=n; i++) { sum = prev + next prev = next next = sum }return sum
}
Copy the code

2.3.2 while

let fib = function(n) {
    let i = 2
    let,1,1 res = [0]while(i <= n) {
        res[i] = res[i - 1] + res[i - 2]
        i++
    }
    return res[n]
}
Copy the code