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!

@lesterpierson123 Special thank you for example input and putting your time to create a minimal verifiable example — Ivan
– Ivan, Commented Oct 18, 2016 at 19:03

Community · Accepted Answer · 2020-06-20 09:12:55Z

3

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;
}

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Oct 18, 2016 at 18:40

Ivan

3,83618 silver badges20 bronze badges

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

4 Comments

lesterpierson123 Over a year ago

What do you mean by the impossible case at the bottom?

lesterpierson123 Over a year ago

I'm also having a hard time understanding your implementation of the deque StatestoExplore...

Ivan Over a year ago

@lesterpierson how it works: we start from initial position(state) and with each action we can move to another step. We can only explore one step at a time, so whenever we have multiple alternatives, we record them (by pushing possible states to the statesToExplore queue) and then we examine one of them. Examination will often give us more steps to check. In the end we'll arrive to a place where no further steps will lead to adding new valid steps (e.g. all of the steps will be outside of the bounds).

Ivan Over a year ago

Also that last return is not that impossible. It means we've tried all the possible states and never hit the target condition return true which means we should return false

Collectives™ on Stack Overflow

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

1 Answer 1

Data structures rule the world of performance

Converting to the iterative form

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Data structures rule the world of performance

Converting to the iterative form

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related