Learning JavaScript Data Structures and Algorithms edition 3: Fibonacci sequences are another problem that can be solved recursively. It is a sequence of 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, etc. The number 2 is obtained by 1 + 1, the number 3 is obtained by 1 + 2, the number 5 is obtained by 2 + 3, and so on. The Fibonacci sequence is defined as follows.
- The Fibonacci number for position 0 is zero.
- The Fibonacci number for 1 and 2 is 1.
- The Fibonacci number for n (where n > 2) is the Fibonacci number for (n-1) plus the Fibonacci number for (n-2).
function fibonacciMemoization(n) {
const memo = [0.1]; / / {1}
const fibonacci = (n) = > {
if(memo[n] ! =null) {console.log('memo! =null--index='+n, 'val='+memo[n])
return memo[n]; / / {2}
}
memo[n] = fibonacci(n - 1) + fibonacci(n - 2); / / {3}
console.log('memo index='+n, memo)
return memo[n]
};
return fibonacci;
}
let num= fibonacciMemoization(5) (5)
console.log('num', num)
Copy the code
In the code above, we declare a memo array to cache all the results of the calculation (line {1}). If the result has already been evaluated, we return it (line {2}), otherwise we evaluate the result and add it to the cache (line {3}).
Take a look at the console print:
- memo! =null–index=1 val=1
- memo! =null–index=0 val=0
- memo index=2 (3) [0, 1, 1]
- memo! =null–index=1 val=1
- memo index=3 (4) [0, 1, 1, 2]
- memo! =null–index=2 val=1
- memo index=4 (5) [0, 1, 1, 2, 3]
- memo! =null–index=3 val=2
- memo index=5 (6) [0, 1, 1, 2, 3, 5]
- num 5
According to the printed content, the analysis can get the calculated running track, see the following figure
Recursion is an example application of stack data structure. After starting from a node, the results will pop up from the call stack layer by layer only after the baseline condition is triggered. It is a last-in, first-out data operation mechanism. Like an upside-down tree, you iterate from top to bottom, left to right, and then bottom to top to compute the result. Only after you compute each subtree, you continue to iterate through the right-hand subtree
Since the Fibonacci numbers for position 2 under position 4 and position 3 under position 5 have already been calculated on the blue arrow trajectory, the next calculation will return results 1 and 2 without continuing to disassemble and iterate