CODEWITHSUNDEEP
c++arrayssortingrecursion
noobCoder
noobCoder

Reputation: 1

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;
}

Upvotes: -1

Views: 107

Answers (1)

derpirscher
derpirscher

Reputation: 17400

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);
}

Upvotes: 2

Related Questions