A 2 dimensional array with a size of NxN, composed of 1 and 0.

A neighbor is a 1 in the north / south / west / east of the index

Recursively find how many neighbors an index in the array has (neighbors that touch other neighbors are also included).

For the array I built I should get 6, but instead I get a stack overflow exception, and I don't get why.

Below is my 7x7 array, that for index 2, 5 should return the value of 6.

Example:

static void Main(string[] args)
{
    int[,] arr = { 
       { 0,0,0,1,0,0,0 },
       { 1,0,0,1,1,0,0 },
       { 0,0,0,0,1,1,0 },
       { 0,0,0,0,1,0,0 },
       { 0,0,0,0,0,0,0 },
       { 0,1,1,1,1,0,0 },
       { 1,0,0,1,0,0,0 } 
    };

    Console.WriteLine(Recursive(arr,2,5));
    Console.ReadLine();
}

Routine under test:

static public int Recursive(int[,] arr, int x, int y) 
{   
    if (x < 0 || y < 0 || x > arr.GetLength(0) || y > arr.GetLength(1))
    {
        return 0;
    }
    
    // check if a 1 has neighbors
    if (arr[x, y] == 1)
    {
        return 1   
               Recursive(arr, x - 1, y)  
               Recursive(arr, x   1, y)   
               Recursive(arr, x, y - 1)  
               Recursive(arr, x, y   1);
     }
     else
     {
         return 0;
     }                   
}

CodePudding user response：

Please, note that when you compute Recursive(arr, x, y) you call both Recursive(arr, x - 1, y) and Recursive(arr, x 1, y):

return 1   
       Recursive(arr, x - 1, y)   // <- both x - 1
       Recursive(arr, x   1, y)   // <- and  x   1
       Recursive(arr, x, y - 1)  
       Recursive(arr, x, y   1);

On the next recursive call, when you try to compute Recursive(arr, x 1, y) it calls Recursive(arr, x 2, y) as well as Recursive(arr, x 1 - 1, y) which is Recursive(arr, x, y). So you have a vicious circle: to compute Recursive(arr, x, y) you must compute Recursive(arr, x, y) and stack overflow as the the result.

The way out is to break the circle and don't let read the same cell again and again (we can just set it to 0 for this):

    public static int Recursive(int[,] arr, int x, int y)
    {
        // out of the grid 
        if (x < 0 || y < 0 || x > arr.GetLength(0) || y > arr.GetLength(1))
            return 0;

        // empty cell   
        if (arr[x, y] == 0)
            return 0;

        // do not read the cell again! From now on treat it as an empty cell
        arr[x, y] = 0;

        int result = 1; // the cell itself

        // let have a loop instead of four calls
        for (int d = 0; d < 4;   d)
            result  = Recursive(arr, x   (d - 2) % 2, y   (d - 1) % 2);

        // Restore after the recursive call:
        // let us do not damage arr with permanently setting cells to 0
        // and return arr to its original state
        arr[x, y] = 1;

        return result;
    }

Edit: non recursive solution, where we memorize in visited all the visited cells:

public static int Memoization(int[,] arr, int x, int y) {
  if (x < 0 || y < 0 || x > arr.GetLength(0) || y > arr.GetLength(1))
    return 0;

  if (arr[x, y] == 0)
    return 0;

  int result = 0;

  var agenda = new Queue<(int x, int y)>();
  agenda.Enqueue((x, y));

  var visited = new HashSet<(int x, int y)> { (x, y) };
 
  while (agenda.Count > 0) {
    result  = 1;
    var (oldX, oldY) = agenda.Dequeue();

    for (int d = 0; d < 4;   d) {
      int newX = oldX   (d - 2) % 2;
      int newY = oldY   (d - 1) % 2;

      if (newX < 0 || newY < 0 || newX > arr.GetLength(0) || newY > arr.GetLength(1))
        continue;
      if (arr[newX, newY] == 0)
        continue;
      if (visited.Add((newX, newY)))
        agenda.Enqueue((newX, newY));
    }
  }

  return result;
}

CodePudding user response：

Start by considering the simplest possible input. In this case it would be an array like

int[,] arr = { {1, 1 }}

I.e. an array consisting of only two items.

1. Start by the first left item, this is one, so next all neighbors recursed to.
2. All but the right neighbor is outside the array so will be ignored.
3. The right item is one, so all neighbors to this will be recursed to, including the left item.

Since you end up processing the left item again, you will continue the recursion until you run out of stack space.

The point here is that you need to keep track of all the points you have already visited. For example by using a HashSet<(int x, int y)>.