Getting an infinite recursion error in java

Question

I cannot find the reason why my code doesn't work. It keeps saying that there's a infinite recursion error. I'm basically trying to solve a maze recursively.

The start and end of the maze are represented with the characters + and -, respectively. The first line of the maze file will be the number of rows and columns, respectively.As your program moves through the maze the current path should also be marked with the + character. Any path leading to a dead end should be marked with the . character. Here is the maze:

https://drive.google.com/file/d/1l15E0Iqvkp-mnPP_vbTfvx93RXjAJzRo/view?usp=sharing

import java.io.*;
import java.util.*;
public class Main {
    public static char[][] maze;
    public static int rows, cols, beginR, beginC;
    public static boolean solve = false;

    public static void main(String[] args) {
        boolean load = loadmaze("maze.txt");
        if (load == false) { 
            System.out.println("Failed to load Maze"); 
            return;
        }

        if (solverMaze(beginR, beginC)) { 
            System.out.println("Congrats you beat the Maze!");
        }
        else {
            System.out.println("Not found");
        }
        pMaze();


    }

    public static boolean loadmaze(String filename) {
         File file = new File(filename);
        try(Scanner scan = new Scanner(file)) {
            rows = scan.nextInt();
            cols = scan.nextInt();
            scan.nextLine(); 

            maze = new char[rows][cols]; 
            for(int i = 0; i < rows; i++) {
                String lines = scan.nextLine();
                for(int l = 0; l < cols; l++) {
                    maze[i][l] = lines.charAt(l);
                    if(maze[i][l] == '+') {
                        beginR = i; 
                        beginC = l;
                    }
                }
        }
        return true; 
        } catch(FileNotFoundException e) {
            System.out.println("Error in loading file");
        }
          catch(Exception e) {
            System.out.println("Error in read maze");
          }
          return false;
        }
    private static boolean solverMaze(int row, int column) {
        if( row < 0 || column < 0 
           || row >=rows 
           || column >=cols 
           || maze[row][column] == 'X' 
           || maze[row][column] == '.' 
           || solve) {
         return false;
        }
        if(maze[row][column] == '-') {
            solve = true; 
            return true;
        }

        if(maze[row][column] != '+' ) {
            maze[row][column] = '+';
        }

        if(solverMaze(row + 1, column) 
           || solverMaze(row - 1, column) 
           || solverMaze(row, column + 1) 
           || solverMaze(row, column - 1)) {
            return true; 
        }

        maze[row][column] = '.';
        return false;
  }
  private static void pMaze() {
        for (char[] row : maze) {
            System.out.println(new String(row));
        }
    }
}

I tried tinkering with backtracking but I had no luck.

Please post it as text, not an image. We cannot run your code with an image as input. — trincot
– trincot, Commented Feb 19 at 20:32
It might be easier if you just hard code the maze in a string in the program and remove the reading of the file portion. That way it would be a self contained program and easily executable by others. A graphic of a 41x41 maze is ok, but just a visual aid. It's not really usable. — chubbsondubs
– chubbsondubs, Commented Feb 19 at 20:33

rzwitserloot · Accepted Answer · 2025-02-19 20:40:36Z

3

Using static and also using recursion is generally asking for trouble.

Your general approach appears to be: Set the current 'location' to a +, then recurse by looking right, up, down, and left (and those calls will recurse), if we found it, great, if not, set the current 'location' back to a '.' and we have our answer.

This doesn't work: The code that looks 'left' will end up looking 'right', after all.

Your + stuff does nothing: You do not go: "Oh, it's a +, so I don't need to recurse". Your code just says: If it isn't already a +, make it a plus. This:

if(maze[row][column] != '+' ) {
  maze[row][column] = '+';
}

Is identical to:

  maze[row][column] = '+';

After all, after that line, the value of maze[row][column], is +.

You don't actually do anything with that +. You then afterwards set the value to ., so as you recurse, you overwrite your plusses with dots again.

Hence, your algorithm never ends: You recursively look right, which will end up recursively looking left, and that will recursively look right again, over and over.

If you want to walk away from the basic rules of recursion (which is zero shared state, everything is carried by parameters and the values you return), feel free to experiment, but you're not going to get very far without first learning how to debug such things: Write code that shows you each recursive step, prints the grid, and so on. Learn how to step through with a debugger, etc.

answered Feb 19 at 20:40

rzwitserloot

107k6 gold badges74 silver badges104 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

John Bollinger Feb 19 at 21:24

Using non-final static fields is asking for trouble in any non-trivial program, recursion or no, but I'd agree that adding in recursion ratchets the trouble potential up a couple of notches.

rzwitserloot Feb 19 at 23:11

@JohnBollinger In this case, if it hadn't been static, it would go exactly as wrong as it does now. Hence why in this answer I highlight: [A] you use ZERO shared state (no fields at all, it doesn't matter if they are static or not, you cannot modify them inside your recursive code!), [B] .. and therefore communicate solely via parameters and return values. -- these rules aren't an absolute requirement; you can write recursive algorithms whilst writing to shared data. But it gets vastly more complicated when you do that. So, don't - unless you're an expert and know what you are doing.

trincot · Accepted Answer · 2025-02-19 21:15:38Z

The problem is that you don't have a good indication for when a cell was already visited and no recursion should happen from that cell. Currently you don't make a recursive call when the cell has X, - or .. You do make a recursive call when it is (space) or +. But when that same cell is visited again at a deeper level during that recursive call, it will still have +, and you will again make a recursive call, ...etc.

The quick fix would be to reserve + as indication that the cell was visited and not make a recursive call. But for that to work, also the first + should be removed before you start.

So make these changes:

Right before if (solverMaze(beginR, beginC)) { add this statement:
```
maze[beginR][beginC] = ' '; // Remove plus mark 
```
In the big if condition where you test for X and ., also add the case for maze[row][column] == '+', so you exit recursion when hitting a + also.

With these two changes there will be no more recursion stack error. The solution path will be found.

Other remarks

You can simplify this:

if(maze[row][column] != '+' ) {
    maze[row][column] = '+';
}

to just:

maze[row][column] = '+';

The big if does not need to test the solve boolean as no new recursive call will be made when that boolean is set to true.
As the challenge says that you should mark "any path leading to a dead end", you cannot afford to exit recursion as soon as you found the - character. Even then you still need to find any other dead end that you had not visited yet.

As this was not your question, I will leave that remaining challenge for you to work on now that the problem at hand is solved.

Collectives™ on Stack Overflow

Getting an infinite recursion error in java

2 Answers 2

2 Comments

Other remarks

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Other remarks

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related