return -1 does not end function execution

Question

This is my code.

65  int BinarySearch(int key, int array[], int min, int max)
66  {
67      int mid;
68      
69      if (max < min)
70      {
71          return -1;
72      }
73      else
74      {
75          mid = ( max + min ) / 2;
76          if (array[mid] < key)
77          {
78              BinarySearch(key, array, mid + 1, max);
79          }
80          else if (array[mid] > key)
81          {
82              BinarySearch(key, array, min, mid - 1);
83          }
84          else
85          {
86              return 0;
87          }
88      }
89      return 1;
90  }

And when I use it to search for a number that is not in the array the code eventually reaches the "return -1;" line inside the "if (max < min)" condition. At that point I expected this function to stop and go back to the calling function. But instead, GDB shows that it keeps going.

75              if (array[mid] < key)
(gdb) n
77                  BinarySearch(key, array, mid + 1, max);
(gdb) n

Breakpoint 2, BinarySearch (key=6, array=0x7ffffffbdd60, min=5, max=4) at helpers.c:68
68          if (max < min)
(gdb) n
70              return -1;
(gdb) n
89      }(gdb) n
BinarySearch (key=6, array=0x7ffffffbdd60, min=4, max=4) at helpers.c:78
78              }
(gdb) n
88          return 1;
(gdb) n
89      }(gdb) n
BinarySearch (key=6, array=0x7ffffffbdd60, min=3, max=4) at helpers.c:78
78              }

I must be overlooking something simple. Thanks.

Answer 1

It does return, but you have to understand where it returns to. When a return executes, it returns control to the function that called it. In this case, since BinarySearch() recursively calls itself, it returns to the previous execution of BinarySearch() that called the current recursion. It will not go directly back to main or the code that originally called BinarySearch().

Additionally, there's a serious problem with how returns are handled. The short version is that when returning, the recursive calls are not immediately returning to the previous recursion. Instead, they continue to the next line of code. For a more detailed explanation of this, see Pset3 Binary Search problems

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)