How to optimize recursion JavaScript

Question

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.

Please edit to include all relevant information for the question in the post. If the link goes down or changes, future visitors will not have the full context and will make understanding the answers or submitting a new one much harder. — VLAZ
– VLAZ, Commented Aug 10, 2021 at 22:16
In general, CodeWars problems require you to come up with a clever solution that isn't the obvious iteration or recursion, because it's too slow for large inputs. See if you can find a shortcut. — Barmar
– Barmar, Commented Aug 10, 2021 at 22:20
In this problem, you have to find a way to avoid testing every possible order. — Barmar
– Barmar, Commented Aug 10, 2021 at 22:23

Eddy Todd · Accepted Answer · 2021-08-13 13:24:44Z

2

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]))

edited Aug 13, 2021 at 13:24

answered Aug 10, 2021 at 22:52

Eddy Todd

9113 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Dlion1 Over a year ago

Thanks for your respond. I have some thoughts on what u wrote. In my case based on recursion each new computation creates two others and at the and i create a call only for return a value that has already been computed. So it's a big waste of memory and speed. Instead of it u created a two dimensional array where each new computation selects from the previous two, thus narrowing down the scope of the search. But i don't know how it works:/ you do not choose right or left side directly. If you will have some free time please explain what is going on in this two loops.

Collectives™ on Stack Overflow

How to optimize recursion JavaScript

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related