Having trouble checking if an array is sorted using recursion

Question

This is the question : An array is sorted (in ascending order) if each element of the array is less than or equal to the next element.

Write a boolean-valued method named isSorted that accepts an integer array, and the number of elements in the array and returns whether the array is sorted.

Before showing the code : my logic is that an if else-if and else statement should first determine if the size of the array is 0,1,or 2. This is because when the size equals 1 or 2, the program must break. When the size is larger than 2, the program should check arr[size-1] > arr[size-2] and then call the method again with size decremented if that is true and just return false if it is untrue. When I ran that program, the following 2 tests failed : [1,3,2,4] and [2,1,2,3,4]. Because of this I specified that when the size is equal to 2, the method returns false if arr[0] > arr[1] however it didn't work. What am I doing wrong? I don't want to just look up the answer because I am studying for a test so I am sorry if there are repeated answers.

I know the loop is better I just wanted to study recursion

public boolean isSorted(int[] arr, int size) { 


    if(size == 0 || size == 1) { 

         return true; 

    } else if (size == 2) { //this is the part I don't get. 

        if (arr[0] > arr[1]) { 

            return false; 

        } else { 

             isSorted(arr,size-1); 
             return true;   

        }


    } else {

         if (arr[size-1] < arr[size-2]) { 

             return false;  

         } else { 

            isSorted(arr, size-1); 
            return true; 

         }

    }

}

There is not restriction in the posted task that you have to use recursion to solve the task. Using simple for loop actually is better approach — Maxim
– Maxim, Commented Oct 5, 2018 at 16:57

Oleg Cherednik · Accepted Answer · 2018-10-05 16:47:35Z

3

Recursion is not good way to solve this problem. What if your array will be very big and you could get StackOverflowError. Why not to use simple if operator:

public static boolean isSorted(int[] arr, int size) {
    if (arr.length >= 2)
        for (int i = 1; i < arr.length; i++)
            if (arr[i - 1] > arr[i])
                return false;

    return true;
}

answered Oct 5, 2018 at 16:47

Oleg Cherednik

18.3k4 gold badges25 silver badges38 bronze badges

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

Comments

xingbin · Accepted Answer · 2018-10-05 16:51:43Z

1

You need return the result from isSorted, for example, change:

isSorted(arr, size-1); 
return true;

to

return isSorted(arr, size-1);

And, the case else if (size == 2) is redundant. size 2 should have the same logic with size 3, 4, 5, ...

Complete code:

public boolean isSorted(int[] arr, int size) {
    if (size == 0 || size == 1) {
        return true;
    } else {
        if (arr[size - 1] < arr[size - 2]) {
            return false;
        } else {
            return isSorted(arr, size - 1);
        }
    }
}

edited Oct 5, 2018 at 16:51

answered Oct 5, 2018 at 16:33

xingbin

28.4k12 gold badges62 silver badges111 bronze badges

5 Comments

Person Over a year ago

Thank you, can you explain why we have to have a separate else if statement for when the size equals 2?

xingbin Over a year ago

@Person No, it's redundant. When the size is 2, it has the same logic with size 3, 4, 5, ...

Maxim Over a year ago

Seems the size == 0 condition is redundant as well

xingbin Over a year ago

@Maxim It's a corner case. When the original array's length is 0.

xingbin Over a year ago

@Person You might want to learn how to use a debugger. It helps a lot. You can debug with IDEs such as Eclipse, IntelliJ IDEA.

Collectives™ on Stack Overflow

Having trouble checking if an array is sorted using recursion

2 Answers 2

Comments

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related