Recursion stack overflow and I dont understand why

Question

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;
    }                   
}

Welcome to Stack Overflow! This is a good opportunity for you to start familiarizing yourself with [using a debugger](https://stackoverflow.com/q/25385173/328193). When you step through the code in a debugger, which operation first produces an unexpected result? What were the values used in that operation? What was the result? What result was expected? Why? To learn more about this community and how we can help you, please start with the [tour] and read [ask] and its linked resources. — David, Nov 01 '22 at 15:53
Start with a simpler case - a 1x2 array where both values are set to 1, and run the call with coordinates `0,0`. That's going to make a recursive call for `0,1`. Which in turn is going to make a recursive call for `0,0`, which in turn is going to... — Damien_The_Unbeliever, Nov 01 '22 at 15:56

Dmitry Bychenko · Answer 1 · 2022-11-01T18:48:31.823

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;
}

oh, so it basically goes x+ 1 then checks x -1 in an infinite loop because x-1 is the once who called x+1 in the first place? — Nitay Aqawae, Nov 01 '22 at 15:59
@Nitay Aqawae: yes, exactly; and since it's *recursive* call it's *stack* which comes to end. — Dmitry Bychenko, Nov 01 '22 at 16:00
@Nitay Aqawae: one of the possible ways out is to mark visited cell by `0` (let it be temporary empty) to prevent system from checking it again and again and restore the cell into its original state after recursion calls. — Dmitry Bychenko, Nov 01 '22 at 16:31
@rotgers: I can't see how can I use *memoization* (memorizing the result of previous execution) in a simple way here; we can check if we *have visited( cell before instead (is it memoization though?). In this case we can even implement a no-recursive solution — Dmitry Bychenko, Nov 01 '22 at 17:06
@DmitryBychenko yeah never mind, I tried it, and it doesn't work. Disabling the cell and resetting it is a pretty neat trick, thanks! — rotgers, Nov 01 '22 at 17:12

score 1 · Answer 2 · answered Nov 01 '22 at 15:59

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.

Start by the first left item, this is one, so next all neighbors recursed to.
All but the right neighbor is outside the array so will be ignored.
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)>.

Recursion stack overflow and I dont understand why

2 Answers2

Linked