Fibonacci sequence is a very classic algorithm problem in the field of mathematics (algorithms are shaking when writing this sentence), today in five minutes to analyze this problem.

What are Fibonacci numbers?

1,1,2,3,5,8,13,21…… The Fibonacci sequence starts with the third term, and each term is equal to the sum of the first two. The Fibonacci sequence was developed by mathematician Leonardoda Fibonacci using rabbit breeding as an example, so it is also called the rabbit sequence.

Of course, for the purposes of computer science, the question becomes: What is the NTH term of the Fibonacci sequence, given a function f(n)? (n is always a positive integer)

Use recursive implementation

If you have programming experience, recursion will come to mind. A good start is half the battle, and if you can think of recursion, you’re not far off. It is not difficult to see that the recursion rule of sequence can be summarized as follows:

f(n) = f(n- 1) + f(n2 -)
Copy the code

Okay, roll up your sleeves

function fibonacci(num){
    if (num <= 2) {return 1;
    }else{
        return fibonacci(num - 1) + fibonacci(num - 2); }}Copy the code

At first glance, perfect. However, at this time, every Developer who is a little bit of pursuit will say: “Big brother, you do so is not the best solution ah, the number is a little bit bigger than the fried chicken slow.”

Fibonacci with cache

Although people are difficult to tear down, but optimization or to do. I can’t help but think of one of the most common and useful examples of front-end performance tuning: caching. The idea is to save the newly calculated value for future use. Talk is cheap, show u the code

let fibo = (function(){
    let cache = [];
    return function(n){
        if(cache[n] ! = =undefined) {return cache[n];
        }else{
            return cache[n] = (n <= 2)?1 : fibo(n - 1) + fibo(n - 2); }}}) ();Copy the code

At first glance, perfect again. Can it be optimized? Of course. Here, array is used as cache container. When FIBO (50) is calculated, the length of array is 51. Js will set the first 50 items as undefined before assigning the value to the last item, which will naturally affect efficiency. One line of code to optimize:

// let cache = [];
let cache = {};
Copy the code

There is no end to life

Optimization is a knowledge, if you are not willing to give up, I can only send you here, after all, the purpose of this article is to help you recall such a classic topic (escape). If some math god had read this piece of crap, he would have scorned the fact that the backhand is a general term formula, as long as you’re happy.

The last

Happy New Year:)