DEV Community

Ashutosh Sarangi
Ashutosh Sarangi

Posted on • Updated on

Unlocking Efficiency: The Surprising Impact of Memoization on Recursive Functions

Introduction

I recently conducted an analysis comparing the number of times a function executes when using plain recursion versus memoized recursion. The results were surprising! 😱 😱

With plain recursion, the function call count can skyrocket due to repeated calculations of the same values. In contrast, memoized recursion significantly reduces the number of executions by storing and reusing previously computed results.

This experiment highlights the efficiency gains that can be achieved with memoization, making it a valuable optimization technique for improving the performance of recursive algorithms.

The Code difference is only 5 Lines Plain Recurssion of a Fibonacci () (See the Difference 😱 )

No Of times function Executed (Can you read the Number 😅 😵 )

**n Recurssion memorized-recurssion**
10 88 9
15 986 14
30 13,46,268 29
const recursiveFibonacciClosure = (n) => {
    let counter = 0;
    function recursiveFibonacci(n) {
      if (n == 0 || n == 1) {
        return n;
      }
      counter++;

      return recursiveFibonacci(n-1) + recursiveFibonacci(n-2);
    }

    recursiveFibonacci(n);
    console.log(`${counter} No of time this function is executed.`); 
    // For n= 10 it is calling 88
    // n = 15 ==> 986 times function Executed
    // n = 30 ==> 13,46,268 times function Executed
}

recursiveFibonacciClosure(30);


const memorizeRecurssion = (n) => {
    let counter = 0;
    const memo = {};
    function recursiveFibonacci(n) {
      if (n == 0 || n == 1) {
        return n;
      }

       const temp = recursiveFibonacci(n-1) + recursiveFibonacci(n-2);

      if (memo[n]) {
          return memo[n]
      } else {
          memo[n] = temp;
      }
      counter++;

      return temp;
    }

    recursiveFibonacci(n);
    console.log(`${counter} No of time this function is executed.`); 
    // For n= 10 it is calling 9
    // n = 15 ==> 14 times it is executed
    // n = 30 ==> 29 times it is executed
}

memorizeRecurssion(30)
Enter fullscreen mode Exit fullscreen mode

Recursion #Memoization #Coding #Programming #Efficiency #AlgorithmOptimization #SoftwareDevelopment #Javascript #Functional programming

Top comments (1)

Collapse
 
ashutoshsarangi profile image
Ashutosh Sarangi

Thanks @adla_sutej