directory

  1. Fibonacci numbers
  2. The recursive method
  3. Tail-call optimization
  4. Senior function
  5. Map memory optimization
  6. Dynamic programming
  7. cycle

Fibonacci sequence

First of all, the Fibonacci sequence starts at the 0th, respectively

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...Copy the code

So the NTH Fibonacci number is returned according to this rule

Fibonacci numbers, usually denoted by F(n). The resulting sequence becomes the Fibonacci sequence. The sequence starts at 0 and 1, and each successive digit is the sum of the preceding two. In other words:

F (0) = 0, F (1) = 1, F (n) = F (n - 1) + F (n - 2), where n > 1Copy the code

I give you n, please calculate F(n).

Example 1:

Input: 2 Output: 1 Description: F(2) = F(1) + F(0) = 1 + 0 = 1Copy the code

Example 2:

Input: 3 Output: 2 Description: F(3) = F(2) + F(1) = 1 + 1 = 2Copy the code

Example 3:

Input: 4 Output: 3 Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3Copy the code

Second, recursive method

  • Time complexity: O(2^n)

It has been 18 years since I wrote the Fibonacci sequence. Time has passed quickly and I have been busy with business. It is time for the algorithm to go further

/ * * *@param {number} n
 * @return {number}* /
var fib = function(n) {
    if(n === 1 || n === 0 ) return n;
    return fib(n-1) + fib(n-2);
};
Copy the code

The idea of recursion is simple: you keep calling your own methods until n is 1 or 0, and you start returning data layer by layer.

Performance is particularly low when large numbers are computed recursively for two reasons:

① During recursion, each time a new function is created, the interpreter creates a new function stack frame, which is placed on top of the current function stack frame, forming the call stack. Therefore, when the number of recursive layers is too large, the call stack may take up too much memory or overflow. ② Recursion causes a lot of double calculation.

The above two disadvantages of recursion can be solved by tail-call optimization and recursion.

Third, tail call optimization

A tail call is a case in which the last action in a function is a function call: that is, the return value of the call is directly returned by the current function. WikiPad[1] in code, the return value of function B is returned by function A. \

An example 1)

function B() {
    return 1;
}
function A() {
    return B();  // return 1
}
Copy the code

2) Fibonacci sequence

var fib = function(n, current, next) {
    if(n === 1) return next;
    if(n === 0) return 0;
    return fib(n - 1, next, current + next);
};
fib(7.0.1); / / 13
Copy the code

Advanced functions

var fib = function(n) {
  let seed = 1;
	return [...Array(n)].reduce(p= > {
		const temp = p + seed; 
		seed = p;
		return temp;
	},0)}; fib(6);
Copy the code

fivememoryTo optimize the Fibonacci sequence

Optimization adds memory, that is, caches the value of a previously computed sequence and returns the value when it is computed again.

const map = new Map(a)var fib = function(n) {
    if(n < 2) return n

    if(! map.has(n)) { map.set(n, fib(n -1) + fib(n - 2))}return map.get(n)
}
fib(6); / / 8
Copy the code

Dynamic programming

var fib = function(n) {
    let dp = [0.1]
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2]}console.log(dp)
    return dp[n]
};

// fib(6); / / 8
// [0, 1, 1, 2, 3, 5, 8]
Copy the code

Seven cycle

- Time complexity: O(n) - Space complexity: O(n)` ``js function fib (n) { let step = [] step[1] = 1 if ( n >= 2) { step[2] = 2 } if ( n <= 2) { return n } for ( let i = 3;  i <= n; i++) { step[i] = step[i - 1] + step[i - 2] } return step[n-1] }; fib(6); / / 8Copy the code

reference

  • Fibonacci numbers
  • Fibonacci numbers
  • Fibonacci numbers
  • Dynamic programming

conclusion

  • The value of a Fibonacci number is the sum of its last two digits. Learn to use memory to optimize your code
  • To solve for f(n), you just need to know some smaller f(c). We call solving f(c) the “subproblem” of solving F (n), which is DP (Dynamic programming). The solution of the larger problem can be deduced by splitting a problem into several sub-problems and solving these sub-problems separately.
  • The Fibonacci sequence can be realized both recursively and circularly