为什么二进制搜索算法需要返回递归调用？

Question

我正在实施递归二进制搜索，我运行遇到了这个让我很困惑的问题。这是我最初的代码运行:

'''

int recursiveBinarySearch(int* arr, int start, int end, int key){
   int middle = (start + end) / 2;

   if (start >= end)return -1;

   if (arr[middle] == key)return middle;

   if (arr[middle] < key) {
    recursiveBinarySearch(arr, middle+1, end, key);
   }

   if (arr[middle] > key) {
    recursiveBinarySearch(arr, start, middle-1, key);
   }

}

'''

现在，据我所知，一旦达到基本情况，唯一 returned 应该是从基本情况中 returned 的值，因为没有另一个电话是 returning 任何东西。但是，很明显我错了，因为这没有给出正确的答案，而且显然我需要在每个递归调用之前有一个 return 语句才能使该算法起作用，正如我后来发现的那样。所以我的问题是，为什么我们需要 return 声明？我的解决方案不起作用的确切原因是什么？

Answer 1

让我们假设，X 是我们从主函数调用的函数。还有一个函数 Y 被函数 X 调用。函数 Y 进行一些计算并计算 X 的结果。所以你应该只调用函数 Y 和 return 它的结果如下所示。

Y() {
 // Some computation
 return result;
}

X() {
 return Y();
}

main() {
  res = X();
}

现在这样想，每个递归调用都是一个单独的函数，它正在执行一些任务。所以你的 recursiveBinarySearch 函数应该 return 答案但它不能自己计算，所以它调用一些其他函数（在这种情况下是相同的函数，因此调用递归）来获得结果。因此它将继续调用该函数并将问题分解为更小的问题，直到它到达将获得答案的基本情况并最终 return 它。

为什么二进制搜索算法需要返回递归调用？

Why does binary search algorithm require returning the recursive calls?

c++

algorithm

recursion

return

data-structures