c++arrayssortingrecursion

Checking whether an array is sorted via recursion


Could you please explain me the working of following code? This is a function to check if the given array is sorted or not by recursion:

#include<iostream>
using namespace std;

bool sorted(int arr[],int n)
{
    if (n == 1)
    {
        return true;
    }

    // I am confused here when n will reach 1 then it will 
    // return true to `restArray` after that if array is 
    // not sorted then how will `restArray` become false?
    
    bool restArray = sorted(arr+1, n-1);
    
    return (arr[0]<=arr[1] && restArray);
}

int main()
{
    int arr[]={1,6,3,4,5};
    cout<<sorted(arr,5);
    return 0;
}

Solution

  • As in every recursion there are two cases

    First the trivial case if (n == 1): An array of size 1 (ie only a single element) is always sorted. Thus it returns true and stops the recursion

    And if n is still greater than 1, you do the recursive call and check if the array without the first element is sorted (bool restArray = sorted(arr+1, n-1)), then you check if the first element of the array is less than the second element (a[0] < a[1]). (btw I'd probably check for <= here) And finally you combine those two checks with &&.

    So for your example, it will at some point in time check 6 < 3, which will return false thus the overall result will become false.

    But for sake of optimization, I'd suggest to reorder your statements a bit, such that you won't need the recursive call, if the order of the first two elements in the array is already wrong. And as @Scheff's Cat mentioned in the comments: When you convert it to a tail recursion, any decdent compiler will be able to refactor that recursion into a (much cheaper) iteration ...

    And I'd also check for n <= 1 otherwise you might end up in an infinite recursion if you method is (wrongly!) called with n = 0.

    bool sorted(int arr[],int n)
    {
        if (n <= 1)
        {
            return true;
        }
    
        return arr[0] <= arr[1] && sorted(arr+1, n-1);
    }
    

    or even simpler

    bool sorted(int arr[], int n) {
      return n <= 1 
        ? true
        : arr[0] <= arr[1] && sorted(arr+1, n-1);
    }