0

In this program, a randomly generated 2D array is populated with 1's or 0's and I attempt to find a path of 1's (no diagonal movement). I have got the program to work for smaller dimensions of the 2D array, but when the dimensions are too large, the error Exception in thread "main" java.lang.StackOverflowError occurs.

import java.util.Scanner;
import java.util.Random;

public class Daft {
    private int counter = 0;

public static void main(String[] args) {
    Daft punk = new Daft();
    punk.run();
}

public void run() {
    int ans;
    int[][] array;
    int[][] solvedPath;
    do {
        counter = 1;
        array = populate(defineArray(firstDimension(),secondDimension()));
        solvedPath = findPath(array);
        System.out.println("Times before solvable: " + counter);
        print(solvedPath);
        ans = continuity();
    }while(ans != 0);
}

public int[][] findPath(int[][] array) {
    int r = 0, c = 0;
    while(true) {
        array[0][0] = 7;
        if(c == 0 && r == array.length-1) { //reached the bottom left, checks right
            if(array[r][c+1] == 1) {
                array[r][c+1] = 7;
                c+=1;
            } else {
                array[r][c] = 7;
                break;
            }
        } else if(c == array[0].length-1 && r == array.length-1) { //reached the bottom right, checks left
            if(array[r][c-1] == 1) {
                array[r][c-1] = 7;
            } else {
                array[r][c] = 7;
                break;
            }
        } else if(r == array.length-1) { //reached the bottom, checks left/right
            if(array[r][c+1] == 1 && array[r][c-1] == 1) {
                counter++;
                newPath(array);
                break;
            } else if(array[r][c+1] == 1) { //checks right
                array[r][c+1] = 7;
                c+=1;
            } else if(array[r][c-1] == 1) { //checks left
                array[r][c-1] = 7;
                c-=1;
            } else { //end of path
                array[r][c] = 7;
                break;
            }
        } else if(c == 0) { //reached the left, checks right/bottom
            if(array[r][c+1] == 1 && array[r+1][c] == 1) { //checks if path is unique
                counter++;
                newPath(array);
                break;
            } else if(array[r][c+1] == 1) {
                array[r][c+1] = 7;
                c+=1;
            } else if(array[r+1][c] == 1) {
                array[r+1][c] = 7;
                r+=1;
            } else {
                counter++; //path has ended, not solvable
                newPath(array);
                break;
            }
        } else if(c == array[0].length-1) { //reached the right, checks left/bottom
            if(array[r+1][c] == 1 && array[r][c-1] == 1) { //checks if path is unique
                counter++;
                newPath(array);
                break;
            } else if(array[r+1][c] == 1) {
                array[r+1][c] = 7;
                r+=1;
            } else if(array[r][c-1] == 1) {
                array[r][c-1] = 7;
                c-=1;
            } else {
                counter++; //path has ended, not solvable
                newPath(array);
                break;
            }
        } else if(array[r][c+1] == 1 && array[r+1][c] == 1) { //checks if path is unique
            counter++;
            newPath(array);
            break;
        } else if(array[r][c-1] == 1 && array[r+1][c] == 1) { //checks if path is unique
            counter++;
            newPath(array);
            break;
        } else if(array[r][c+1] == 1) { //checks right
            array[r][c+1] = 7;
            c+=1;
        } else if(array[r+1][c] == 1) { //checks bottom
            array[r+1][c] = 7;
            r+=1;
        } else if(array[r][c-1] == 1) { //checks left
            array[r][c-1] = 7;
            c-=1;
        } else {
            counter++;
            newPath(array);
            break;
        }
    }
    return array;
}

public int firstDimension() {
    Scanner in = new Scanner(System.in);
    System.out.println("Size of the first dimension:");
    return in.nextInt();
}

public int secondDimension() {
    Scanner in = new Scanner(System.in);
    System.out.println("Size of the second dimension:");
    return in.nextInt();
}

public int[][] defineArray(int firstDimension, int secondDimension) {
    return new int[firstDimension][secondDimension];
}

public int[][] populate(int[][] array) {
    Random rand = new Random();
    for(int i = 0; i < array.length; i++) {
        for(int j = 0; j < array[i].length; j++) {
            array[i][j] = rand.nextInt(2);
        }
    }
    return array;
}

public int continuity() {
    Scanner in = new Scanner(System.in);
    System.out.println("Enter a number to continue (0 to quit):");
    return in.nextInt();
}

public void print(int[][] array) {
    for(int[] ints : array) {
        for(int anInt : ints) {
            System.out.print(anInt + " ");
        }
        System.out.println();
    }
    System.out.println();
}

public void newPath(int[][] array) {
    findPath(populate(array));
}

}

thequentinbeck
  • 1
  • 1
    What constitutes _"too large"_? A recursive search can take up a lot of stack space, so in this case you might need to increase the stack space with for example `-Xss256m`. If you still get `StackOverflowError` with a much larger stack, then you should check your code. – Jim Garrison Mar 20 '21 at 22:52
  • 5
    Since Java has no [Tail Call Optimization](https://stackoverflow.com/questions/310974/what-is-tail-call-optimization), every recursion will eventually result in a `StackOverflowError` if the recursion is deep enough. Furthermore, since the recursion is not a tail recursion, the only way to really prevent a `StackOverflowError` would be to transform the recursion into an iteration. – Turing85 Mar 20 '21 at 22:52
  • 4
    and there is no reason to use recursion in this solution/code - use a loop (e.g. `while (!found) { populate...found = find(...)}`) –  Mar 20 '21 at 22:55

0 Answers0