Checking whether an array is sorted via recursion

Question

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

Have you stepped through the code with a debugger? I suspect you'll learn a ton doing that. — Stephen Newell
– Stephen Newell, Commented Feb 26, 2022 at 5:46
Is this wacky assignment you were given the same as this one? Recursion to determine if an array is sorted -- no wonder it's confusing, because using recursion makes no sense for this type of work. — PaulMcKenzie
– PaulMcKenzie, Commented Feb 26, 2022 at 9:00
@PaulMcKenzie It's even worse: Think of an array with 10,000 items. The recursion depth would be 10,000. Of course, it will hit a stack overflow before. And even if the first two items are not sorted, it will still go through the entire array. This code should be used to teach programming, as an example of how not to do it. — Codo
– Codo, Commented Feb 26, 2022 at 13:39

derpirscher · Accepted Answer · 2022-02-26 13:10:51Z

2

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

edited Feb 26, 2022 at 13:10

answered Feb 26, 2022 at 7:47

derpirscher

17.7k3 gold badges25 silver badges54 bronze badges

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

6 Comments

noobCoder Over a year ago

when we are checking return (arr[0]<arr[1] && restArray); here arr[0] and arr[1] are constant i.e if 1st & 2nd element of the array are sorted then this condition will always be true so the answer now depends on the variable restArray but when we will reach n==1 it will return true in restArray at any situation now if there is any element after 2nd element which is unsorted that we can only get from restArray bu as we know that restArray is containing true so how will it become false then?

derpirscher Over a year ago

No. Please try debugging through this code, check the values of arr[0] and arr[1] in each recursive call and read about pointer arithmetic in c++. When you pass arr + 1 into the recursive call, you are "skipping over" the first element of the array. arr[0] in the first recurisve call will actually point to the second element of the original array. In the second recursive call it will point to the third element of the original array, and so on and so forth ...

Scheff's Cat Over a year ago

+1 for mentioning the missed optimization in OPs code. I just was about to write a comment about this... ;-) Btw. turning this into a tail recursion might encourage the compiler to flat this out to an iteration which should've be used first hand in real-world projects. -> Et voilà: Test on Compiler Explorer. g++ 11.2 did as expected. (No call found in the generated code.)

derpirscher Over a year ago

@Scheff'sCat Thanks for the comment about tail-recursion. I was thinking about mentioning it while writing the answer. But when I came to part about optimization, I of course forgot about it ...

noobCoder Over a year ago

Thankyou soo much I finally understood it

|

Collectives™ on Stack Overflow

Checking whether an array is sorted via recursion

1 Answer 1

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related