CODEWITHSUNDEEP
javascriptrecursionoptimization
Dlion1
Dlion1

Reputation: 21

How to optimize recursion JavaScript

I am struggling with this codewars problem where I have to find the highest sum by selecting the card on the left or right. I managed to solve this using two recursive calls for each side respectively:

function solve(cards, i, j, sum, x)
{
    if (i > j)
        return sum;   
    
    var left = solve(cards, i+1, j, sum+(Math.pow(2,x)*cards[i]), x+1 );
    var right = solve(cards, i, j-1, sum+(Math.pow(2,x)*cards[j]), x+1 );

    return left > right ? left : right; 
}

I created a diagram in PowerPoint to show how I see my code. It will be like a binary tree:

enter image description here

But the execution of my program is very very slow. Please show me how I can do this better.

Upvotes: 1

Views: 234

Answers (1)

Eddy Todd
Eddy Todd

Reputation: 81

The faster solutions to this problem don't use recursion, they use Dynamic Programming where you store data that might be repeated multiple times if you use recursion. Using recursion, the execution time will increase exponentially with every added element to the card list. Here's a faster solution using Dynamic Programming.

function calc(cards){
  let n = cards.length;
  let dp = Array.from(Array(n), _ => Array(n).fill(0));
  for (let i = 0; i < n; i++) 
    dp[0][i] = 2 * cards[i];
      
  for (let i = 1; i < n; i++) 
    for (let j = 0; j < n - i; j++)
       dp[i][j] = Math.max(dp[i - 1][j] * 2 + dp[0][i + j], dp[i - 1][j + 1] * 2 + dp[0][j]);

  return dp[n - 1][0]
}

console.log(calc([1,2,5]))
console.log(calc([1]))
console.log(calc([1,1]))
console.log(calc([1,2,1]))
console.log(calc([4, 10, 2, 3, 1, 3, 1, 6, 9]))

Upvotes: 2

Related Questions