0

i wrote this isSorted function that will check if the array is sorted or not if the array is sorted, it will return 0, else it will return 1, but for some reason, the function keeps on returning 0 even if the array is not sorted. This is the full program with the function

struct array {

    int A[10];
    int size;
    int length;
};


void displayArray(struct array arr) {
    std::cout << "the elements are :-" << std:: endl << '\t';
    for (int i = 0; i < arr.length; i++) {

        std::cout << arr.A[i] << ',';
    }
    std::cout << std::endl;
    
}

int ifSorted(int *a, int n, int i) {
    if (n >0) {
        
        if (*(a + i) > *(a + 1 + i))
            return -1;

           
        
        else {
            i++;
            ifSorted(a, n - 1, i);

        }
        return 0;
    }
    
}

int main()
{
    struct array arr = {{1,2,3,10,5,6,7}, 10, 7};
    int* p;
    
    std::cout << ifSorted(&(arr.A[0]), arr.length, 0);
}

I tried to debug the program and It works how it is supposed to but instead of returning -1 , it is returning 0.

Improve this question
4
  • 3
    return ifSorted(a, n - 1, i); ... also, if n is less than 1, the function will not return anything. Enable compiler warnings. Note that you probably want the case of an empty array to be considered as "sorted". Commented Feb 21, 2022 at 3:09
  • 4
    recursive function for checking if the array is sorted not working -- It's amazing that so many homework assignments dealing with recursion almost never choose a scenario where recursion would be good to use. IMO, this leaves the student bewildered as to the use-case for recursion. Determining if an array is sorted is easily done by simply writing a loop. It's like learning how to walk by standing on your heels. Commented Feb 21, 2022 at 3:12
  • 1
    Agreed... It's painful to see all these crazy recursion assignments. It's fine if you're using a functional programming language, but very unusual for C++. One other point to make is that apart from all the things we've already identified about this function being incorrect, it also will not correctly handle the array size of 1. In that case, it happily accesses the element past the end of the array. Commented Feb 21, 2022 at 3:15
  • a[i] > a[i + 1] would be more readable than *(a + i) > *(a + 1 + i) Commented Feb 21, 2022 at 3:35

1 Answer 1

Reset to default
0

but instead of returning -1 , it is returning 0

When you write return -1; that value is only passed back to the caller. Now, at that point, you might be several calls deep into the recursion. The line from the call immediately before is this:

ifSorted(a, n - 1, i);

So, what happens is after that call returns, you discard the return value of -1 and continue executing from this call. You ultimately then return 0, because that is the next statement.

To fix this, you must pass back to the caller whatever the recursive call returned:

return ifSorted(a, n - 1, i);

Now, you have some other problems too. To begin with, let's see what happens if n is zero (or negative)...

int ifSorted(int *a, int n, int i) {
    if (n > 0) {
        // this code is never reached
    }
    // there is no return value
}

This is a problem. You have undefined behavior for a very important case. At some point, if everything is already in sorted order, your final recursion will ask whether an empty array is sorted. Of course, it is, but your function must return something. So let's fix that:

int ifSorted(int *a, int n, int i) {
    if (n > 0) {
        // this code is never reached
    }
    return 0;
}

Now, let's think about one other special case. What if there's only one element in the array (i.e. n is 1)? Well, you're doing this:

if (*(a + i) > *(a + 1 + i))
    return -1;

But the problem is that *(a + 1 + i) is the element past the end of the array.

So actually, your "zero-size array is sorted" logic really should extend to "zero- or one-size array is sorted". That will solve that nasty problem.

On another note, I'd recommend you don't use pointer arithmetic for accessing your array elements. Use array indexing. The compiler will generate the same instructions, but the code is easier for humans to read.

if (a[i] > a[i + 1])
    return -1;

Furthermore, it's not very "recursion-friendly" to add the parameter i. That's kinda showing that you're still thinking of it like a loop. Instead, recursion is about breaking a problem down into smaller problems. What you can do is advance the array pointer by 1 when you reduce its size by 1. That makes i utterly redundant.

Finally, because the function never intends to modify the array's contents, it's best to enforce that by declaring a as const. This way, your function can operate on arrays that are already const, and you can't accidentally write code that modifies the array because that will be a compiler error.

Phew.... Well, let's put all of this together:

int ifSorted(const int *a, int n)
{
    if (n < 2)
        return 0;
    else if (a[0] > a[1])
        return -1;
    return ifSorted(a + 1, n - 1);
}
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Side-note: using &(arr.A[0]) is too verbose. Allow the compiler to elide the array to a pointer, and your call from main becomes: ifSorted(arr.A, arr.length)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.