Looking for help on a java assignment from school I am tryin

Looking for help on a java assignment from school, I am trying to create a recursive algorithm that solves the following puzzle: Given a starting position and an array of length n consisting n-1 positive numbers with the last position of the array being 0, for example: {4 8 5 2 3 5 1 6 4 0}

The rules of the game: From starting position move to right equal to the value @ starting position, repeat until you can no longer move to the right. Once you can no longer move to the right, move left in similar fashion as you moved to the right and stop once you can no longer move to the left. Now keep repeating this process. The puzzle will be solved when you have moved the last position of the array holding value of 0. Otherwise the puzzle is unsolvable.

In the above example if we start @ first position which is \'4\' We move to the right 4 positions ending up @ position 5 holding value 3

We move to the right 3 positions ending up @ position 8 holding value 6

We move to the left 6 positions ending up @ position 2 holding value 8

We move to the right 8 positions ending up @ last position holding value 0

since we have moved to the last position of the array, the puzzle is solvable. I have to solve this puzzle using recursion, I have come up with the algorithm and it works fine except when the game has an impossible configuration in which STACK OVERFLOW Error occurs. The impossible game / puzzle would be where the array has values like this: { 5 8 2 3 1 5 0 }

in the above array example, the algorithm will keep looping between the two 5\'s if i start at index 0 or index 2 or index 4. When such array is randmoly generated, my algorithim gets in a loop and throws stack overflow error and finally terminates.

static boolean rightWing(int[] A, int i) //i = starting position
{
int left=i;
int right=A.length-i-1;
  
if (A[i]<=right&&A[i]!=0)
{
i=i+A[i];
return rightWing(A, i);
}
if (A[i]<=left&&A[i]!=0&&!checkImpossible(A,i))
{   
i=i-A[i];
return rightWing(A,i);
}
if (A[i]==0)
return true;
else
return false;
}

static boolean checkImpossible(int[] B, int i) // helper methoed to check if the game is stuck, BUT does not work all the time, sometimes StackOverflowException Occurs,
{
boolean impossible=false;   
for (int j=i-B[i];j<=i;j=j+B[j])
{
int left=j,right=B.length-j-1;
if (B[j]==B[i]&&j==i||(B[j]>right&&B[j]>left))
{impossible=true;
break;}
}
return impossible;

Solution

import java.io.*;

class PushZero

{

    // Function which pushes all zeros to end of an array.

    static void pushZerosToEnd(int arr[], int n)

    {

        int count = 0; // Count of non-zero elements

        // Traverse the array. If element encountered is

        // non-zero, then replace the element at index \'count\'

        // with this element

        for (int i = 0; i < n; i++)

            if (arr[i] != 0)

                arr[count++] = arr[i]; // here count is

                                       // incremented

        // Now all non-zero elements have been shifted to

        // front and \'count\' is set as index of first 0.

        // Make all elements 0 from count to end.

        while (count < n)

            arr[count++] = 0;

    }

    /*Driver function to check for above functions*/

    public static void main (String[] args)

    {

        int arr[] = {1, 9, 8, 4, 0, 0, 2, 7, 0, 6, 0, 9};

        int n = arr.length;

        pushZerosToEnd(arr, n);

        System.out.println(\"Array after pushing zeros to the back: \");

        for (int i=0; i<n; i++)

            System.out.print(arr[i]+\" \");

    }

}