CODEWITHSUNDEEP
javascriptmultidimensional-arraydata-structures
Gourav Singh Rawat
Gourav Singh Rawat

Reputation: 441

Maximum call stack size exceeded error during recursive calls

I've been trying to solve a recursion question islandPerimeter

/**
 * @param {number[][]} grid
 * @return {number}
 */
var islandPerimeter = function (grid) {
  let visitedLand = new Set();

  function dfs(i, j) {
    if (i < 0 || j < 0 || i > grid.length || j > grid[0].length || grid[i][j] == 0) return 0;
    if (visitedLand.has({ i: j })) return 1;

    visitedLand.add({ i: j });

    let perimeter = dfs(i, j + 1);
    perimeter += dfs(i + 1, j);
    perimeter += dfs(i, j - 1);
    perimeter += dfs(i - 1, j);

    return perimeter;
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[0].length; j++) {
      if (grid[i][j]) {
        return dfs(i, j);
      }
    }
  }
};

let nums = [
  [0, 1, 0, 0],
  [1, 1, 1, 0],
  [0, 1, 0, 0],
  [1, 1, 0, 0],
];
islandPerimeter(nums);

I've initialised this function of dfs()inside my main function but it shows this...

function dfs(i, j) {
              ^
RangeError: Maximum call stack size exceeded

if (i < 0 || j < 0 || i > grid.length || j > grid[0].length || grid[i][j] == 0)
                                                                          ^
TypeError: Cannot read properties of undefined (reading '1')

There's two for() loops that first calls this dfs function and inside it I'm again calling them. Please explain what's this issue, I've read a few threads that this is regarding over calling the recursion. Anyway to fix this?

Upvotes: 1

Views: 113

Answers (1)

Heiko Thei&#223;en
Heiko Thei&#223;en

Reputation: 16728

When the expression {i: j} occurs twice in your code, they are two distinct objects. Therefore, the Set does not recognize the second object as the same as the first:

> visitedLand.has({1: 2})
false
> visitedLand.add({1: 2})
Set(1) { { '1': 2 } }
> visitedLand.has({1: 2})
false

As a consequence, the return 1; statement is never reached, and the recursion goes on ad infinitum.

Use strings i + "-" + j rather than objects.

Also, replace

i > grid.length || j > grid[0].length

with

i >= grid.length || j >= grid[0].length

because grid[grid.length] is already undefined.

Upvotes: 2

Related Questions