how to traverse a Boolean recursion array

The exercise: Build a recursion(with no loops) that every cell that you go inside is the number of steps that you can go, it could be right/left until you get to the last cell. if you can’t get to the last cell return false, else return true. you must start from index 0.

My problem: I build the program, it’s not working, ,i am able to get to last cell but in the output i get false, i understand why i get false but i don’t know how to fix it.

Test:

public static void main(String[] args)
{
// Q - isWay
        System.out.println("nTesting Question 3n==================");
        int[] a1 = {2,4,1,6,4,2,4,3,5};
        System.out.println("a = {2,4,1,6,4,2,4,3,5}");
        System.out.println("Ex14.isWay(a) is: " + Ex14.isWay(a1)); //need to return true
        int[] a2 = {1,4,3,1,2,4,3};
        System.out.println("a2 = {1,4,3,1,2,4,3}");
        System.out.println("Ex14.isWay(a2) is: " + Ex14.isWay(a2));//need to return false
}


public class Ex14
{
    public static boolean isWay(int[] a)
        {
            int i = 0;
            if(a.length <= 1)
                return false;
            return isWay(a , 0);
        }

        public static boolean isWay(int[] a,int i)
        {     
            int temp1 , temp2;
            if(i == a.length-1)
                return true;
            if(!((a[i]+i < a.length) && (i-a[i] >= 0))) // can't go right and left
                return false;
            else if(a[i] > 0)
            {
                if(a[i]+i < a.length) // go right
                {
                    temp1 = a[i] + i;
                    a[i] = -1;
                    return isWay(a, temp1);
                }
                else if (i-a[i] >= 0) // go left
                {
                    temp2 = i - a[i];
                    a[i] = -1;
                    return isWay(a, temp2);   
                }    
            }
            return false;
        }
}

Answer

Your condition for returning false is wrong.

if(!((a[i]+i < a.length) && (i-a[i] >= 0)))

should be

if(!((a[i]+i < a.length) || (i-a[i] >= 0)))

You want to return false if you can’t proceed either left or right. Your condition tests whether you can’t proceed both left and right.

EDIT:

My original suggested fix wasn’t enough, since your method must be able to back-track if you reach a dead end.

Here’s an alternative approach:

public static boolean isWay(int[] a,int i) {
    int temp1 , temp2;
    if(i == a.length-1) {
        return true;
    }
    boolean found = false;
    if(a[i]+i < a.length && a[a[i]+i] > 0) { // go right
        temp1 = a[i] + i;
        a[i] = -1;
        found = isWay(a, temp1);
        if (!found) {
            a[i] = temp1 - i; // must restore a[i] to its original value, in order 
                              // to be able to go left
        }
    }
    if (!found && i-a[i] >= 0 && a[i - a[i]] > 0) { // go left
        temp2 = i - a[i];
        a[i] = -1;
        found = isWay(a, temp2);   
    }
    return found;
}

The idea is that if you can go both left and right, and going right leads to a dead end, you must try to go left when the recursive call for going right returns.

This returns true for both {1,4,3,6,1,2,4,3} and {2,4,1,6,4,2,4,3,5}.