1. Title Description

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, train of thought analysis

If you know the Fibonacci sequence, and then you add the formula that they’re giving you, you basically know how to write it. For example, n = 5 represents the fifth level of the Fibonacci sequence

0: 0 1: 1 2: 0 + 1 = 1 3: 1 + 1 = 2 4: 1 + 2 = 3 5: 2 + 3 = 5 6: 3 + 5 = 8...Copy the code

So as long as you’re dealing with the boundary case that returns 0 for 0, 1 for 1, and (n-1) + (n-2) for everything else, you can just use recursion to solve this problem.

AC code

Method 1:

var fib = function(n) {
    if(n < 2) return n

    return fib(n - 1) + fib(n - 2)
}
Copy the code

Method 2: optimization adds memory, that is, caches the value of the previously computed sequence and returns the value when it is computed again.

const map = new Map() 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) }Copy the code

Four,

The value of a Fibonacci number is the sum of its last two values. Learn to use memory to optimize code.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign