Getting an infinite recursion error in java - Stack Overflow

admin管理员组

文章数量:1289403

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:

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.

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/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.

• java
• recursion
• error-handling
• overflow
• stack-overflow

Share Improve this question Follow edited Feb 19 at 20:56 chubbsondubs 38.9k2525 gold badges109109 silver badges142142 bronze badges asked Feb 19 at 20:17 Cool DudeCool Dude 111 bronze badge 8

• What is in "samplemaze.txt"? – Scott Hunter Commented Feb 19 at 20:23
• i posted the maze – Cool Dude Commented Feb 19 at 20:30
• Please post it as text, not an image. We cannot run your code with an image as input. – trincot Commented Feb 19 at 20:32
• 1 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 Commented Feb 19 at 20:33
• 2 Have you tried running your code in a debugger? – Old Dog Programmer Commented Feb 19 at 20:50

 |  Show 3 more comments

2 Answers 2

Sorted by: Reset to default 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.

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:

1. Right before if (solverMaze(beginR, beginC)) { add this statement:

   maze[beginR][beginC] = ' '; // Remove plus mark 
   

2. 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.

本文标签： Getting an infinite recursion error in javaStack Overflow