-1

This function is from my professor's notes:

int ints_is_sorted_r(int* a, int n){
    return n <= 1 || (a[0] <= a[1] && ints_is_sorted_r(a+1, n-1));
}

This is my version with many printfs to see what it does

int ints_is_sorted_r(int* a, int n){

    printf("n <= 1 = %d\n",(n <=1));
    printf("a[0] <= a[1] = %d <= %d\n",a[0],a[1]);
    ints_println_special(a,n);
    return n <= 1 || (a[0] <= a[1] && ints_is_sorted_r(a+1, n-1));

}

(ints_println_special() is a function from my prof's library that prints the whole array)

My question is, how does the recursion stop? Here's the output from my test:

enter image description here

My guess is that when you have an OR condition and the first one is true it doesn't waste time looking for the right side of the condition because it knows it's going to be true anyway. Am I correct?

4
  • Google for "short circuit evaluation". See softwareengineering.stackexchange.com/questions/201896/…. Commented Dec 8, 2019 at 21:56
  • @Carcigenicate: OR if first evaluand is TRUE // AND if first evaluand is FALSE will both short-circuit. Commented Dec 8, 2019 at 22:04
  • @Carcigenicate No worries! If there were "Whoops" badges on S.O., I'd have earned several gold ones, already. 😊 Also, your comment helped me improve my answer (the PS) - hope you don't mind. Commented Dec 8, 2019 at 22:16
  • 1
    Tip: posting text as a picture rather than text attracts down votes. Text as text is more useful. Commented Dec 8, 2019 at 22:52

1 Answer 1

1

My guess is that when you have an OR condition and the first one is true it doesn't waste time looking for the right side of the condition because it knows it's going to be true anyway. Am I correct?

Yes, you are correct! It's called "short-circuiting" and there are several good posts here on Stack Overflow that explain and discuss it, like this one.

PS: Note that there could also be (probably will be) such short-circuiting, internally, in the part after the || operator; so, in (a[0] <= a[1] && ints_is_sorted_r(a+1, n-1)), if the first comparison, a[0] <= a[1], is FALSE, then the second won't be evaluated, and the function won't be called recursively in that case.

1
  • If you think an answer on another question would explain it better, you should vote to close as duplicate of that question instead of answering.
    – S.S. Anne
    Commented Dec 8, 2019 at 22:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.