passing an array of arrays into a recursive function in javascript

Question

I'm trying to do this problem where you are given an array of arrays. You start at the first item and them move either 1 item to the right or 1 item down depending on which item is bigger. the goal is to make it to the bottom right corner with the highest sum possible. Maybe I'm missing the point, but I figured this was a recursive function.

let map = [
        [8,3,5],
        [4,3,4],
        [2,2,3]
    ]

const find = (y,x,map) => {

    if (y === map.length - 1 && x === map[map.length - 1].length - 1){
        return map[y][x]
    } else if(map[y + 1][x] > map[y][x + 1]){
        return map[y][x] + find(((y + 1), x,map))
    } else {
        return map[y][x] + find((y,(x + 1),map))
    }

}

 console.log(find(0,0,map))

In this case the goal is to get 22 via 8->4->3->4->3, but whenever I pass the map into the next level of recursion, the array on the next level reads as undefined. Is there any way to pass down the array of arrays so that it can be read by other levels of the recursive function?

8+4+3+4+3 = 22, but if you go 8+3+5+4+3 you get 23. So your algorithm to find the path with highest total is flawed. You want an actual pathfinding algorithm. — Niet the Dark Absol
– Niet the Dark Absol, Commented Jun 10, 2020 at 11:16
This isn't a recursive problem, When the array is 2 dimensional you can solve it just by changing your x and y coordinates. — dehart
– dehart, Commented Jun 10, 2020 at 11:24
@NiettheDarkAbsol it's not flawed - it's sinful! ...because it's greedy :P — VLAZ
– VLAZ, Commented Jun 10, 2020 at 11:26

Nina Scholz · Accepted Answer · 2020-06-10 11:31:10Z

1

If you like to get the greatest sum by moving only right or down, you could take an recursive approach by creating an exit condition first, with the last possible value and then take another exit condition if indices are out of bound (meybe here is a value of -Infinity better to omit this value).

Then take the real possible value and decide which value you like to return for getting a maximum.

const find = (map, i = 0, j = 0) => {
    if (i + 1 === map.length && j + 1 === map[map.length - 1].length) return map[i][j];
    if (i === map.length || j === map[map.length - 1].length) return 0;
    let a = find(map, i + 1, j),
        b = find(map, i, j + 1);

    return map[i][j] + (a > b ? a : b);
}

let map = [[8, 3, 5], [4, 3, 4], [2, 2, 3]];

console.log(find(map));

answered Jun 10, 2020 at 11:31

Nina Scholz

388k26 gold badges367 silver badges417 bronze badges

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

Collectives™ on Stack Overflow

passing an array of arrays into a recursive function in javascript

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related