This is the 22nd day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

A, definitions,

Fibonacci number fib(n), also known as the golden ratio, starts with 0 and 1. Colloquially, the fib(n) number is the sum of the first two numbers.

For example: 0,1,1,2,3,5,8,13,21,34,55,89…

It can be solved by recursion, cache and recursion. And Fibonacci has mathematical formulas, matrices, bitwise operations and so on.

Second, the recursion

var fib = function(N) { if(N == 1 || N == 0) { return N; } return fib(N-1) + fib(N-2); }}Copy the code

Ideas:

  • It prints when N is given to you equal to 1 or equal to 0
  • Otherwise we recursively take the first N number and the first two numbers, and then we figure out that the sum of these two numbers is the current N.

Use recursion to output the NTH number of the sequence, but because Fibonacci is repeated a lot using recursion, you can use mathematical formulas to speed it up. Because N is getting larger and larger, the larger the value of N, the more likely it is to cause memory overflow, or long calculation time, as shown in the figure above, the calculation speed is very slow, although it can be implemented, but only for numbers between 0 and 30.

Third, recursive

Definition: Recursive calculation method is a representative of ideal thinking mode, according to known conditions to reach an intermediate conclusion, until the result is derived, recursive calculation method is also divided into two kinds of backward and forward.

  • Derivation: Based on known conditions, to find the result to be solved.
  • Reverse: according to the current problem, step by step to find the conditions.

The difference between recursion and recursion: recursion removes the process of moving data in and out of the stack, that is, it does not need to go through the function to the boundary value, but backwards from the boundary value to the function value. So recursion is more efficient, but recursion also has the advantage of being able to use it on demand.

var fib = function(N) { let cache = []; for(let i = 0; i <= N; i++) { if(i == 1 || i == 0) { cache[i] = i; }else { cache[i] = cache[i-1]+cache[i-2] } } return cache[N] }Copy the code

This is order n, but it can be better mathematically.

The first time to write an algorithm, if there is a bad place to write do not say me ah, social fear……