// This is a function to check if the given array is sorted or not by recurssion

#include<iostream>
using namespace std;
bool sorted(int arr[],int n)
{
    
    if(n==1)
    {
        return true;
    }
    // I am cofused 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;
}

CodePudding user response：

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