Recursive boolean if an array is ordered

Question

My task is to use a recursive boolean method to find out if or if not an array with its indexes I give to the method is sorted in an up-counting way. I solved the non-recursive task but I'm stuck now cuz IDK how to make a recursive method which has to give an array every time... here my idea

public static boolean isSortedRecursive(int[] a) {

    int k=a.length-1;
    int z=a[k];
    int v=a[k-1];

    if(z>v){

        return false;
    }

    else if(z<a.length){
        k--;
        isSortedRecursive(a);
        return true;


    }


    isSortedRecursive(a);
    //return false;

}

Let me know if the solution helps. For recursion, first try to come up with a recursive formula in plain simple English words. Then, write the formula and code. — Adithya Upadhya
– Adithya Upadhya, Commented Apr 19, 2020 at 18:11

Adithya Upadhya · Accepted Answer · 2020-04-19 18:12:19Z

1

This is a fairly straightforward answer. Try to understand what's going on.

Recursively speaking, an array until index i is sorted in ascending order if the array till i - 1 is sorted and array[i - 1] <= array[i].

public static boolean isArraySorted(int[] a, int i) {  

   if (a.length == 0 || i == 0) {
       return true; // Empty array or we're at the first element of the array.
   }

   return a[i - 1] <= a[i] && isArraySorted(a, i - 1);
}

// Test code
int[] a = new int[]{1, 2, 3, 4, 5, 5, 6};

isArraySorted(a, a.length - 1);

Frankly speaking, recursive code for this is an overkill since it takes O(N) space and time. I understand your course instructor would've intended to get your "feet wet" with recursion. But, it's not the best use of recursion.

edited Apr 19, 2020 at 18:12

answered Apr 19, 2020 at 18:04

Adithya Upadhya

2,41325 silver badges28 bronze badges

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

Comments

Arvind Kumar Avinash · Accepted Answer · 2020-04-19 18:14:30Z

1

By adding one more parameter (size of array), you can make it fairly simple as follows:

public class Main {
    public static void main(String args[]) {
        // Tests
        System.out.println(isSortedRecursive(new int[] { 2, 3, 1, 4, 7, 5, 6 }, 7));
        System.out.println(isSortedRecursive(new int[] { 6, 1, 3, 5, 7, 4, 2 }, 7));
        System.out.println(isSortedRecursive(new int[] { 1, 2, 3, 4, 5, 6, 7 }, 7));
    }

    public static boolean isSortedRecursive(int[] a, int size) {
        if (a[size - 1] < a[size - 2]) {
            return false;
        }
        if (size > 2) {
            return isSortedRecursive(a, size - 1);
        }
        return true;
    }
}

Output:

false
false
true

Note: It will return true only for an array sorted in ascending order.

edited Apr 19, 2020 at 18:14

answered Apr 19, 2020 at 18:09

Arvind Kumar Avinash

81k10 gold badges98 silver badges144 bronze badges

Collectives™ on Stack Overflow

Recursive boolean if an array is ordered

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related