optimization for javascript recursive

Question

So, I have this task:
Where n is a positive integer, the function f(n) satisfies the following

f(0) = 0 
f(1) = 1
f(n) = f(n-1) + f(n-2) when n > 1

1. Please create a program to find f(n)

2. Use the program to find f(8181)

   const f = (n) => {
     if(n === 0) {
       return 0
     } else if(n === 1) {
       return 1
     } else if(n > 1) {
       return f(n-1) + f(n-2)
     } else {
       return null
     }
   }
   

above is the code that i have wrote but it only do just fine when i do n < 40, it starts to slow down when n > 41. it takes forever to load f(100) let alone f(8181)
so, is there any way to optimized this code to meet all the requirements?
thank you in advance!

ps: it's not a school task so i dont have anyone to consult

Answer 1

You can use memoization to optimize the algorithm.

The idea is to remember the result of f(n - 1) + f(n - 2) in a JS object so that further calculations can use the memoized result instead of re-calculating everything.

Following is a demo, which instantly prints the result for f(100) correctly.

let dict = {};

const f = (n) => {
  if (n === 0) {
    return 0
  } else if (n === 1) {
    return 1
  } else if (n > 1) {
    if (!dict[n]) {
      dict[n] = f(n - 1) + f(n - 2);
    }

    return dict[n];
  } else {
    return null
  }
}

console.log(f(100));

Answer 2

@31piy - Avoid using recursion as it is not memory efficient also because each function is getting pushed in call-stack which slows down program. Here is the program for Fibonacci series till n number without recursion.

Hope this will help you :)

/**
 * Method to return Fibonacci series with linear (without recursion)
 * @param {*} n 
 */
function getFibonacciSeries(n){
    var n1 = 0, n2 = 1, a = [], n3;
    a.push(n1);
    a.push(n2);
    for(i=2; i < n; i++){
        n3 = n1 + n2;
        a.push(n3);
        n1 = n2;
        n2 = n3;
    }
    console.log(a);
    return a[n-1];
}