The recursive implementation

function fibonacc(n) {
  if (n === 0) {
    n = 0;
  } else if (n === 1) {
    n =  1;
  } else {
    n =  fibonacc(n - 1) + fibonacc(n - 2);
  }
  return n
}
Copy the code

The call stack

  • The JS engine parses out the global context and executable code
  • The global context is then pushed onto the stack, executing executable code and encountering function calls
  • Parse the function into the same two parts, pushing the function context onto the stack
  • Popup updates the global context after execution
  • Recursion is simply pushing the stack over and over again, hitting the top and then bouncing and updating the context at the next level.
  • Note the context only

Optimized recursion – Tail recursion

function fibonacc2(n) {
  return fibonacc3(2, n, 1, 0);
}
function fibonacc3(start, end, prev1, prev2) {
  if (start === end) {
    start = prev1 + prev2;
  } else{ fibonacc3(start + 1, end, prev1 + prev2, prev2); }}Copy the code

Note that simply putting recursion at the end of a function is not tail-recursion.

function fibonacc(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return  1;
  } else {
    returnfibonacc(n - 1) + fibonacc(n - 2); }}Copy the code

Fibonacc (n-1) still needs its return value to add after it finishes, so the fibonacc(n) environment must be saved for processing the return value.

  • Tail-recursion: To enter an environment where the next function does not need the previous function, and return directly after the result.
  • Non-tail recursion, the function continues after the next function ends, so it must save its own environment for processing the return value.
  • Tail recursion usually takes one more parameter, which is the result of the last call to the function. Tail recursion collects the result each time

But JS will still stack even if the next function no longer needs the previous function’s environment, so JS has no tail recursive operations.

Loop instead of recursion

function fibonacc4(n) {
  let fibArray = [0, 1];
  for (let i = 0; i <= n - 2; i++) {
    fibArray[i + 2] = fibArray[i + 1] + fibArray[i];
  }
  return fibArray[fibArray.length - 1];
}
Copy the code

Memory,

Even though the last piece of code was done with an array and recorded the values, it’s not memorization, like if n was 5 one time and 4 the other time, you still have to compute the whole thing the second time

function memozi(fn) {
  const cache = {};
  return function(n) {
    if (cache[n] == null) {
      cache[n] = fn(n);
      return cache[n];
    } else {
      returncache[n]; }}; } const fibfn = memozi(function (n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    returnfibfn(n - 1) + fibfn(n - 2); }});Copy the code
  • Use a hash table to record all the results completely
  • To compute the NTH one, you have to go to memory and find fibfn(n-1) + fibfn(n-2).
  • We’ll just use the function returned by Memozi, and if the memory lookup fails then Memozi’s callback will be called to do the calculation
  • Memorization: When the callbacks in Memozi do not change, the values are retrieved from memory
  • Memozi is also done using closures. Memozi creates and hides a cache and returns a function fn. Each call to FN does not recreate the cache, but only modifies it

Raect remembered

Does the memorized code above look like the React Memo hook?

React The parent component function is re-executed every time the data changes, and the child component function inside it is also re-executed. Although the DOM is not updated, the code in the child component is re-executed (the resulting DOM is still the same as last time, so the page is not updated).

child2 = React.memo(child)
Copy the code

but

<child2 onClick = {()=>{}}/>
Copy the code

Even if it is memorized, child2 will be re-executed when clicked, because the onClick function creates a new function every time it is clicked, and child2 will re-execute if it thinks it is different

let x = ()=>{}
<child2 onClick = {x}/>
Copy the code

This will still re-execute child2 because the parent component will re-execute, redeclaring x each time.

We need to mnemonize the function: we use n as the memory index, and as long as n does not change the function does not change

let x = React.useCallback(()=>{},[n])
Copy the code

summary

  • The mnemonization of fibonacc is indexed by n
  • React indexes rely on us to provide data for indexing