Memoization in recursive functions, javascript

Question

Memoization in recursive functions, javascript

Navigation

#1 by (6 votes)

2

function fibo(num) {
  if(num == 0) {
    return 0;
  } else if(num == 1) {
    return 1;
  } else {
    return fibo(num-1) + fibo(num-2);
  }
}

This is my code to resolve fibonacci in javascript, but I do fibo (50) it hangs. I have been researched about the memo and how to apply it in recursive functions, but I still do not understand could you help me?

javascript

asked by Jóse M Montaño 23.08.2018 в 01:08

source

1 answer

How can I put together a predicate function when I have to choose between several options How can I get the latest registration by date and time

score 6 · Accepted Answer

Here is fibonacci in the memo version, which is not simply more than saving the values that have already been calculated. Something like this:

var cache = {1:1, 2:1};
function fib(n) {
    if(!cache[n]) // Ya calculamos este valor?
       cache[n] = fib(n - 1) + fib(n - 2)  // Calcular y guardar

    return cache[n]
}

console.log(fib(50));