Click here to Skip to main content
15,868,016 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
Trying to understand this recursive solution for the count islands problem.

I lose track after the 4th recursive call since my console.log(grid)
Shows me the next 1 to turn to a 0 is row 3, col 0.
However, my mind says it should've been row 0 col 1.

I know the continue statement breaks an iteration and continues with the next.


grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","1"]
]


function numIslands(grid) {
    const H = grid.length;  // 4
    const W = grid[0].length; // 5

    let count = 0;
    
    for (let r = 0; r < H; r++) { // Row
      for (let c = 0; c < W; c++) { // Col
        if (grid[r][c] === '0') continue;
        
        count++; // 3
        dfs(r, c);
      }
    }
    return count;
    
    function dfs(r, c) { // Gets called first time with (0, 0)

      if (r < 0 || c < 0 || r === H || c === W) return; // Checks if out of bounds.
      if (grid[r][c] === '0') return; 
      console.log("Row: ",  r, "Col: ", c)
      
      grid[r][c] = '0'; // (0, 0) turns from  1 to 0.
      dfs(r-1, c); // (-1, 0) returns due to out of bounds
      dfs(r+1, c); // (1, 0) turns from 1 to 0.
      dfs(r, c-1); // (0, -1) retuns due to out of bounds
      dfs(r, c+1); // 
    }
  }

  console.log(numIslands(grid))


What I have tried:

Testing/breaking this down for a couple of hours +.
Other recursive solutions for this exact problem and understanding them.
Posted
Updated 21-Jan-23 17:03pm

Here is an example using a recursive function:

let arr = [{id:1}, {id:2}, {id:3}, {id:4, children:[{id:5}, {id:6}]}];

function countObjects(arr) {
    let count = 0;
    arr.forEach(function(element) {
        if (element.children) {
            count += countObjects(element.children);
        }
        count++;
    });
    return count;
}

console.log(countObjects(arr));


In this example, the countObjects function takes in an array of objects as a parameter. Inside the function, we initialize a count variable to 0. Then we use the forEach method to iterate over each element of the array. If the element has a children property, we call the countObjects function again and pass the children property as an argument. This will recursively count the number of objects in the children array. Then we increment the count by 1, and return the count.

In this example, the output will be 6, as there are 6 objects in the array.

Another way to implement this is using the reduce method

let arr = [{id:1}, {id:2}, {id:3}, {id:4, children:[{id:5}, {id:6}]}];

function countObjects(arr) {
    return arr.reduce((acc, cur) => acc + (cur.children ? countObjects(cur.children) : 0) + 1, 0);
}

console.log(countObjects(arr));


This will also return 6 as the output.

It's important to note that this recursive solution could cause stack overflow if the tree is too deep, so it's important to have a base case to stop the recursion.
 
Share this answer
 
Comments
Chris Aug2022 21-Jan-23 20:12pm    
Thanks for the reply, but I am trying to understand the recursive function in my post.
I understand how recursion works, although the one I posted is not very clear after the 3rd dfs call.

Also, can you see solution 1? It says yours is solution 2 and I got an email for solution 1 but solution 1 doesn't appear.
Nelek 22-Jan-23 4:26am    
Because it was most probably not folloging the rules of the site and got deleted.
I gather that this is not your code. Here is how I read it (without running it)...

0 = off
1 = on

1. dfs is passed a point (r, c).
2. It checks if out of the bounds of the array (recursion only), then we are done.
3. It checks if it is off, then we are done.
4. Sets the cell to off, then it looks in all 4 directions (goto step 1.)

You have 3 Islands.
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900