Check if an array is sorted or not using recursive approach!

Problem Statement:

You will have given an array. You need to find out if the array is sorted in ascending order or not. Remember equal values are allowed.

Approach:

Let's follow the below algorithm:

• If the length of the array is 0 or 1, return true. (Base Condition)

• Check if the last two values of the array are sorted. Make a recursive call with a decrement in the length of the array. If values are not sorted return false.

• If all values will be sorted, then the length of the array will be 1 and the base condition will hit.

Solution:

The following code is in JavaScript:

function isArraySorted(arr, n) {
    /*
     * base case
     * 1. if array length is (0||1) 
     * that means we don't need to validate.
     * 2. if array already checked all values using recursive call.
    */
    if (n == 1 || n == 0){
        return true;
    }

    /*
     * 1. if first value is greater than second from last.
     * 2. Equal values are allowed.
    */
    if (arr[n - 1] < arr[n - 2]){
        return false;
    }

    /*
     * Make recursive call
    */
    return isArraySorted(arr, n - 1);
}

let sampleArray = [10, 20, 20, 40, 80, 90];
let length = sampleArray.length;
let ans = isArraySorted(sampleArray, length);
console.log({ ans });

console.log('--------------');

sampleArray = [10, 20, 20, 100, 80, 90];
length = sampleArray.length;
ans = isArraySorted(sampleArray, length);
console.log({ ans });

Output:

You will able to see the following output in the console.

{ ans: true }
--------------
{ ans: false }

Time Complexity: O(n) Auxiliary Space: O(n) for Recursion Call Stack.

Happy Codings 🧑🏼‍💻