1
$\begingroup$

I was looking at a recursive solution for the robot on a grid problem which basically states that there is a robot on the top left corner on a grid and you are supposed to find a path to the bottom right of the grid and the robot can only move down or to the right. Below is the recursive function for the solution

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        // If there's a path from the start to my current location, add my location.
        if (isAtOrigin || getPath(maze, row, col - 1, path) || getPath(maze, row - 1, col, path)) { 
            Point p = new Point(row, col);
            path.add(p);
            return true;
        }

        return false;
    }

I understand the solution, at every recursive call it checks if it is at the bottom right or if going down one step or going right one step takes it to the bottom right.

However I was thinking that this solution only works because there are only two possible next steps (down or right) that we are easily able to hardcode and connect with the || operator. But what if there were N different next steps? In that case we would need to call the recursive getPath() function within a for loop from 1 to N. But then how would we check if any of the 1 to N recursive calls return True? In this case it would not be possible to connect all of them with an || operator. Would something like the following work?

public static boolean getPath(boolean[][] maze, int row, int col, ArrayList<Point> path) {
        // If out of bounds or not available, return.
        if (col < 0 || row < 0 || !maze[row][col]) {
            return false;
        }

        boolean isAtOrigin = (row == 0) && (col == 0);

        if(isAtOrigin){
            Point p = new Point(row, col);
            path.add(p);
            return true;
         }

         for(int i:N){
             if(getPath(maze,row,col-i,path)){
                Point p = new Point(row, col);
                path.add(p);
                return true;
             }
         }

        return false;
    }

Is this a valid solution for the change in the problem that I suggested? I think what is throwing me off here is that in the original solution all the recursive calls are made at the same time within the if statement, but here they are called sequentially in the for loop. Is that still valid?

$\endgroup$
  • $\begingroup$ This seems like a programming question, so off-topic here. $\endgroup$ – Yuval Filmus Sep 9 '18 at 4:38
1
$\begingroup$

The way that that the short-circuit expression A || B is evaluated is as follows:

if A is True:
   return True
return B

In words:

  • Run $A$. If it returns True, return True. Otherwise, continue.
  • Run $B$, and return the result.

In particular, $A$ and $B$ are not run in parallel; they are run in sequence.

There is absolutely no problem generalizing this to a short-circuit OR of larger arity:

if A1 is True:
   return True
if A2 is True:
   return True
...
if An is True:
   return True
return False

We could also replace the last bit with simply return An, to make it match the previous pseudocode, but the form above is perhaps more easy to implement using a loop.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.