Is my recursion ok? Are there any examples that break the code?

Question

Given a square integer matrix A NxN, 2<=N<=100 which represents a maze. The elements of the matrix with values grater than 0 are passable, and the others are not passable. Decreasing path is every path in the maze formed by passable elements for which every next element is either on the right or down the previous element.

Write a function bool reachable(int A[][100], unsigned N, int sx, int sy, int target), which checks whether there exists a decreasing path from the element with coordinate (sx,sy) to an element with value "target", for which the elements of the path form non-decreasing sequence.

For example:

 1  0  1  0

10 15  1  1

50 20 50 50

40  0 40 60

there exist such path from element with coordinates (0,0) to element with target=60, but does not exist such path from the same element to element with target=40.

So here is my attempt:

#define N 4
#include <iostream>
bool reachable(int A[N][N], int n, int x, int y, int target)
{
    if (x < 0 || y < 0 || x >= n || y >= n) return false;  
    if (A[x][y] == target) return true;

    if (A[x][y] <= A[x][y + 1])
    {
        if (reachable(A, n, x, y + 1, target)) return true;
        else return false;
    }
    if (A[x][y] <= A[x + 1][y])
    {
        if (reachable(A, n, x + 1, y, target)) return true;
        else return false;     
    }
    return true;
}
int main()
{
    int A[N][N] = { { 1, 0, 2, 0},
                    {10,15, 2, 2},
                    {50,20,50,50},
                    {40, 0,40,60} };
    std::cout << reachable(A, N, 0, 0, 60);
}

Are there any bugs and contraexamples that break the code? I'm not so good with the recursion.

Answer 1

Consider the call reachable(A, N, 0, 0, 2) for this matrix:

1  1  1  1

1  0  0  1

1  0  0  0

1  1  1  2

Your code will follow the path {0,0}->{0,1}->{0,2}->{0,3}->{1,3}->{2,3} and return false afterwards. The problem occurs because of this statement:

if (A[x][y] <= A[x][y + 1])
{
  if (reachable(A, n, x, y + 1, target)) return true;
  else return false;
}

If this if-else statement is entered, the code will ignore the next one, which checks the other possible path. So in my example the second path is totally ignored.

Here is the fixed variant:

• added checks that you cannot turn right if y==n-1 or down if x==n-1;
• deleted wrong return statements after recursion calls;
• added last return statement return false for the case, when no path from current point exists

bool reachable(int A[N][N], int n, int x, int y, int target)
{
  if (x < 0 || y < 0 || x >= n || y >= n)
    return false;

  if (A[x][y] == target)
    return true;

  // if possible to turn right, check this path
  if (y + 1 < n && A[x][y] <= A[x][y + 1])
  {
    if (reachable(A, n, x, y + 1, target))
      return true;
  }

  // if possible to turn down, check this path
  if (x + 1 < n && A[x][y] <= A[x + 1][y])
  {
    if (reachable(A, n, x + 1, y, target))
      return true;
  }

  // no path exists
  return false;
}