recursive function for checking if the array is sorted not working-CodePudding

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.

CodePudding user response：

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