Converting a recursive method into a non-recursive method using loop in java

Question

So I'm currently making a game where the instructions are to move left or right within an array using the integer stored at a marked index (circle in this case) until we can get the circle to the last index of the array. The last integer of the array is always 0.

For example,

[4] 1 2 3 1 0, here we start at the circle 0 (index)

We move 4 to the right, 4 1 2 3 [1] 0

Then 1 time to the right, 4 1 2 3 1 [0]. Here the game stops and we win.

My code is as follows for a recursive method:

public static boolean rightWing (int circle, int[] game, List<Integer> checkerList){

int last = game.length-1;

if (circle == last){ // base case for recursion
    return true;
}

if (circle < 0){ // if we go out of bounds on the left
    return false;
}

if (circle > last){ // if we go out of bounds on the right
    return false;
}

if (checkerList.contains(circle)){ // check for the impossible case 
    return false;
}

checkerList.add(circle); // adds the circle value for the last check to checkerList so we can check for the impossible case

int moveRight = circle + game[circle]; // these two integers help the game move according to the value of the int at circle
int moveLeft = circle - game[circle];

return rightWing( moveRight, game, checkerList) || rightWing(moveLeft, game,checkerList);
}

This works great, but the only problem is it's recursive and slow. I'm trying to redesign it using loops and stacks/queues to make it more efficient, but I'm stuck after writing this (in pseudo):

   Boolean rightWing (int circle, List<int> game, List<int> checkerList)

Int lastPlace = game.size() - 1

For int i <- 0 to game.size() - 1 do

    If i equals lastPlace then // returns true when i is at the last position of the game
        Return true

Any input on how to go forward would be appreciated!

Answer 1

The most important bit: when debugging app for the slowness, you should collect some performance data first to identify where your app is spending the most of its time. Otherwise fixing performance is inefficient. You can use jvisualvm it's bundled with jdk.

Data structures rule the world of performance

One thing why it can be slow is because of this:

if (checkerList.contains(circle)){ // check for the impossible case 
    return false;
}

The more items you have in the list, the slower it becomes. List has linear complexity for the contains method. You can make it constant complexity if you'll use HashSet. E.g. if you have list with 100 elements, this part will be around slower 100 times with List than with HashSet.

Another thing which might be taking some time is boxing/unboxing: each time you put element to the list, int is being wrapped into new Integer object - this is called boxing. You might want to use IntSet to avoid boxing/unboxing and save on the GC time.

Converting to the iterative form

I won't expect this to affect your application speed, but just for the sake of completeness of the answer.

Converting recursive app to iterative form is pretty simple: each of the method parameters under the cover is stored on a hidden stack on each call of your (or others function). During conversion you just create your own stack and manage it manually

public static boolean rightWingRecursive(int circle, int[] game) {
    Set<Integer> checkerList = new HashSet<Integer>();
    Deque<Integer> statesToExplore = new LinkedList<>();
    
    int last = game.length - 1;
    
    statesToExplore.push(circle);
    
    while (!statesToExplore.isEmpty()) {
        int circleState = statesToExplore.pop();
        
        if (circleState == last) { // base case for recursion
            return true;
        }

        if (circleState < 0) { // if we go out of bounds on the left
            continue;
        }
        
        if (circleState > last) { // if we go out of bounds on the right
            continue;
        }
        
        if (checkerList.contains(circle)) { // check for the impossible case
            continue;
        }
        
        checkerList.add(circle); // adds the circle value for the last check to
        // checkerList so we can check for the
        // impossible case
        int moveRight = circle + game[circle]; // these two integers help the
        // game move according to the
        // value of the int at circle
        int moveLeft = circle - game[circle];
        statesToExplore.push(moveRight);
        statesToExplore.push(moveLeft);
    }

    return false;
}