Recursive function Help

I have code here with a maze that uses a recursive function to solve the maze and then prints out all the coordinates from start to exit.

%  clear workspace
clearvars;
clear global MAZE ROWLIMIT COLLIMIT ROWEND COLEND

%  maze, its size, and endpoint must be global
global MAZE ROWLIMIT COLLIMIT ROWEND COLEND

%  maze
 MAZE(1,:) = '############';
 MAZE(2,:) = '#   #      #';
 MAZE(3,:) = '  # # #### #';
 MAZE(4,:) = '### #    # #';
 MAZE(5,:) = '#    ### #  ';
 MAZE(6,:) = '#### # # # #';
 MAZE(7,:) = '#  # # # # #';
 MAZE(8,:) = '## # # # # #';
 MAZE(9,:) = '#        # #';
MAZE(10,:) = '###### ### #';
MAZE(11,:) = '#      #   #';
MAZE(12,:) = '############';

%  constants & initial values
ROWLIMIT = 12;
COLLIMIT = 12;
rowbegin = 3;
colbegin = 1;
ROWEND = 5;
COLEND = 12;

%  solve the maze -- (0,0) is a dummy "previous" value 
isPathToExit(0, 0, rowbegin, colbegin);

This is the code I written so far for the recursive function 'isPathToExit':

function success = isPathToExit(previous_row, previous_col, current_row, current_col)
% Finds a path from entrance to exit through the maze

% base case
global MAZE ROWLIMIT COLLIMIT ROWEND COLEND
if current_row == ROWEND && current_col == COLEND
    disp(sprintf('(%i, %i)', current_row, current_col));
    success = true;
    return;
else
    success = false;
end
% recursion
if current_row+1 ~= previous_row && MAZE(current_row+1, current_col) ~= '#' && current_row+1 ~= ROWLIMIT && current_row ~= 0 
    success = isPathToExit(current_row, current_col, current_row+1, current_col);
    if success
        disp(sprintf('(%i, %i)', current_row+1, current_col));
        return;
    end
end
if current_row-1 ~= previous_row && MAZE(current_row-1, current_col) ~= '#' && current_row-1 ~= ROWLIMIT && current_row ~= 0
    success = isPathToExit(current_row, current_col, current_row-1, current_col);
    if success
        disp(sprintf('(%i, %i)', current_row-1, current_col));
        return;
    end
end
if current_col+1 ~= previous_col && MAZE(current_row, current_col+1) ~= '#' && current_col+1 ~= COLLIMIT && current_col ~= 0
    success = isPathToExit(current_row, current_col, current_row, current_col+1);
    if success
        disp(sprintf('(%i, %i)', current_row, current_col+1));
        return;
    end
end
if current_col-1 ~= previous_col && MAZE(current_row, current_col-1) ~= '#' && current_col-1 ~= COLLIMIT && current_col ~= 0
    success = isPathToExit(current_row, current_col, current_row, current_col+1);
    if success
        disp(sprintf('(%i, %i)', current_row, current_col-1));
        return;
    end
end

When I run it, it displays the points up to a wall of the maze and stops. I need it display the points from start to exit.

Answer 1

[Alex]

A few comments: 1. using global variables, then settings and clearing them is a bad habit to get into.

2. disp(Maze(i,j)); will not show the coordinates, it'll only show the element of the Maze that is the current position, which all of those should be " " white space.

If you want the indicies, use:

disp(sprintf('The current maze index is %i and %i, current_row, current_col));

3. Your if statements are very hard to read. Also, you're putting the recursive statements within the if statement itself, I would recommend separating those. This makes debugging easier. Additionally, you don't need to have all those conditions based on row_limit, col_limit, and such. Since the entire maze is surounded by '#', all you need to do is check in the 3 remaining directions for a solution

ex:

function success = Recursive_Fcn(prev_row, prev_col, next_row, next_col)
   if (at maze exit)
       sucess = true
       return
   else
    sucess = false;
   end
    if(prev pt was not from up && up point is clear && ~sucess )
       sucess = recursive statement(up direction)
       if(success)
          print pt
         end
    end
    if(prev pt was not from down && down point is clear && ~sucess )
       sucess = recursive statement(down direction)
       if(success)
          print pt
       end
    end
    if(prev pt was not from lwft && left point is clear && ~sucess )
       sucess = recursive statement(left direction)
       if(success)
          print pt
       end
    end
    if(prev pt not from right && right pt is clear && ~success)
       success = recursive statement(right direction)
       if(success)
          print pt
       end
    end

     return

I made these changes to your code and got it to work.

[Taylor]

When you run it, does it list all the coordinates that lead to the exit?

[Taylor]

I made the changes you did and now matlab closes when I run it.

[Alex]

This was my output -

The current index is 5 and 11

The current index is 4 and 11

The current index is 3 and 11

The current index is 2 and 11

The current index is 2 and 10

The current index is 2 and 9

The current index is 2 and 8

The current index is 2 and 7

The current index is 2 and 6

The current index is 3 and 6

The current index is 4 and 6

The current index is 4 and 7

The current index is 4 and 8

The current index is 4 and 9

The current index is 5 and 9

The current index is 6 and 9

The current index is 7 and 9

The current index is 8 and 9

The current index is 9 and 9

The current index is 9 and 8

The current index is 9 and 7

The current index is 9 and 6

The current index is 9 and 5

The current index is 8 and 5

The current index is 7 and 5

The current index is 6 and 5

The current index is 5 and 5

The current index is 5 and 4

The current index is 4 and 4

The current index is 3 and 4

The current index is 2 and 4

The current index is 2 and 3

The current index is 2 and 2

The current index is 3 and 2

The current index is 3 and 1

So, it's the solution, but backwards.

Additionally, I had to add in an "exit" condition. I didn't account for that in my last post.

[Alex]

Ohh, also, I found a mistake in your recursive calls.

Each of the calls should be (current_row, current_col, next_row, next_col).

3 of the calls you have are (current_row, previous_col, next_row, next_col)

[Taylor]

Oh ok.

How would I write an exit condition?

[Alex]

I modified my original post with better pseudo code for you.

If Matlab is still crashing, I would guess that it is from too many recursive statements. I would recommend going through each itteration to see what is happening (what direction the solution is going) compared to where you think it should go.

[Alex]

I kind of cheated for my exit condition. Since I knew the exit is the only other element (besides the entrance) on the border that isn't a '#' character, I knew that I would recieve an error when the MATRIX tried to go anywhere from that exit point. So, I used a try/catch, where the try would see if I was at the matrix border, if it errored, the catch would throw and I would return a true.

There are other options for exit conditions. Your original idea about keeping track of the # rows is another option.

[Taylor]

Shouldn't there be a return in each if statement?

[Alex]

It's not needed in this case. If you look at the pseudo code, the addition of each if statement (directional statement) has the addition of the term (&& ~success).

That extra term will skip the other if statements if the correct path was found. Thus exiting at the last return statement of the function.

[Taylor]

I posted my updated code for the function following your pseudo. However, nothing happens when I run it.

[Taylor]

I think I did the if (success) part wrong.

[Alex]

within your if's, it should be:

success = isPathToExit(current_row, current_col, current_row+1, current_col);

if success

disp(sprintf('(%i, %i)', current_row+1, current_col));

end

OR -

if isPathToExit(current_row, current_col, current_row+1, current_col)

disp(sprintf('(%i, %i)', current_row+1, current_col));

end

You're currently running the recursion twice on each step.

[Alex]

Also, looking at your code, you and I handle success a little differently. You'll want the returns in each if block. That'll fix an issue where the matrix tries to go out of bounds if you don't.

(I avoided this with the previous mentioned try/catch)

[Taylor]

Yeah. That's my issue now. I get this:

??? Attempted to access MAZE(0,1); index must be a positive

integer or logical.

[Taylor]

I updated my code above. Still, I'm getting that error.

[Alex]

I see an error within one of your direction sub-functions.

This is a statement error, versus a processing error. Using debugging statements & debugging mode will help you track down where the functionality of your program is making a mistake.

I'll give this hint: make sure each of the recursive statements represents the correct direction it is suppose to go.

[Taylor]

I think I see what you saw.

It was current_row+1 when it should be current_col+1

When I run it now, there no error but nothing is displayed.

[Alex]

use disp functions to see what is happening - I.e. see where the recursion is stalling out.

[Alex]

Also, your if direction functions look like this (for the down case):

if(previous point not from down && direction is clear && row not max && success )

The last two parts of this are not longer needed. The && ~success isn't needed because you have a return for each time success is true. Also, the row/col not max isn't need assuming your initial "at final location" condition is correct (and it was working for me fine) - (also, you're only looking at the condition where the col/row could be at the max, you aren't looking at the min, which also should be considered if you take this approach).

[Taylor]

if isPathToExit(current_row, current_col, current_row+1, current_col)

Is this actually calling the recursive function?

I wondering if this is why it's not displaying the points.

[Taylor]

I changed my code around.

Now when I run it, it displays the points up until it hits a wall, then stops.

Your output is correct.

For some reason, it's not going backwards after hits a wall and finds the exit.

[Alex]

Track your code using the debugging mode. Follow and see where the breakdown is occurring.

[Taylor]

When it reaches a dead end, it just stops like it is trapped and doesn't return to find another path. I can't figure out what I need to add or change to my code to fix this. Can I see the way you wrote your code? I feel I'm missing some little obvious piece.

[Alex]

Is your code hopping between 2 points at a dead end? like going from 11-5 to 11-6 to 11-5 ....

Or, is it just ending? If it is ending, is there an error that it is ending with?

[Alex]

If your current code the code above?

[Alex]

I found a problem

if success == isPathToExit(current_row, current_col, current_row+1, current_col)

end

This if statement is wrong. First, isPathToExit is being analyzed, and then that result is compared to success. Which, at that point, success is false, so you are actually looking for when the recursive statement is false.

Look again at my pseudo code.

success = recursive statement()

if success

Trying to combine multiple steps like this can cause problems. Breaking them apart allows you to easier study what it happening in the code and find a problem.

[Alex]

The other way you could do this is

if recursive statement

success = true

return

But again, the first way is easier to track what is happening in the code, because you can explicitly see what the recursive function is returning before it is being passing into the IF statement

[Taylor]

Okay. Now I get this error:

??? Attempted to access MAZE(2,13); index out of bounds because

size(MAZE)=[12,12].

But how?

[Alex]

Running your code, these are the steps (locations) it is taking. You can see 2 times where it is making mistakes. It should NEVER enter (11,8) or (2,12). Both of these spots are filled with '#'.

(3, 1)

(3, 2)

(2, 2)

(2, 3)

(2, 4)

(3, 4)

(4, 4)

(5, 4)

(5, 5)

(6, 5)

(7, 5)

(8, 5)

(9, 5)

(9, 6)

(9, 7)

(10, 7)

(11, 7)

(11, 8)

(11, 9)

(11, 10)

(11, 11)

(10, 11)

(9, 11)

(8, 11)

(7, 11)

(6, 11)

(5, 11)

(4, 11)

(3, 11)

(2, 11)

(2, 12)

I did 2 things to find the answer.

1. after the exit statement, I put a disp message displaying the current maze pt.

2. after each directional if statement (and before the recursive statement), I put a disp message saying what direction the algorithm has choosen to go.

I want you to find the answer without me giving it to you directly. You'll understand how to debug programs better in the future by following step like this.

[Taylor]

I figured it out. I had to switch the last two conditions for each direction.

Now I get the correct output. Finally.

Thanks for the help.

[Alex]

+ the answer please.