return 语句在递归中是如何工作的？

Question

#include<iostream>
using namespace std;

int binarySearch(int a[], int size, int x, int low, int high){
    if(low > high) return -1;

    int mid = (low + high)/2;

    if(a[mid] == x){
        return mid;
    }

    if(a[mid] < x){
        return binarySearch(a, size, x, mid+1, high);
    }
    else{
        return binarySearch(a, size, x, low, mid-1);
    }
}

int main(){
    int a[] = {1, 2, 3, 4, 5, 6};
    int size = sizeof(a) / sizeof(a[0]);
    cout<<binarySearch(a, size, 5, 0, size-1);
}

例如，在这个使用递归执行二进制搜索的程序中，我对 return binarySearch(a, size, x, mid+1, high);.

语句中 return 关键字的用法感到困惑

这里忽略不写return关键字的警告，这里不写return会有什么不同。它在内部会有所不同还是相同。在什么情况下 return 语句在此类语句中变得有用。

Answer 1

如果您不从非 void-return 类型的函数中 return，它将导致 undefined behavior。从逻辑上讲，它应该仍然可以正常运行，但从技术上讲，在某些编译器上它可以运行，在其他编译器上它可能不行。

在启用 -Wreturn-type 的情况下在 gcc 上编译也会给您一个警告（正如您所提到的）：

warning: no return statement in function returning non-void [-Wreturn-type]

例如拿这段代码：

#include <iostream>

int foo() {
   int a = 5;
   int b = a + 1;
}

int main() { std::cout << "Test:"; std::cout << foo(); } // may print 6

从我的编译器 (gcc (MinGW.org GCC-6.3.0-1) 6.3.0) 中，它确实打印 Test:6，尽管没有 return。但在其他编译器上，它可能什么都不做、崩溃等...

一个例子：ideone.com

所以最好return使用得当。

相关：Why does flowing off the end of a non-void function without returning a value not produce a compiler error?

Answer 2

好吧，当您指定函数的 return 类型时，当 control-flow 从函数中遗漏时，函数确实期望 return 某个值。

所以一个函数，int function() 应该 return 一个整数类型的值，这是标准的。

现在，在你的程序中，你已经将数组分成两半，并且从之前调用创建的一半中的一个又分成两半，你一直在这样做，直到并且除非你有找到了值，或者你已经用尽了所有的一半（就二进制搜索而言，这是有效的）。

让我们彻底了解一下：

    Let's say you have an array {1, 2, 3, 4, 5, 6, 7} and key {2}

所以在二进制搜索方面，由于数组的中间 4 是你正在寻找的非元素，你会把数组分成两半，你会考虑左边的子数组，因为中间的 {4} 大于您正在搜索的元素：

         left_sub_array = {1,2,3,4} and right_sub_array = {5, 6, 7}

你会再次做同样的事情，你会停下来 return key/index，因为：

since the middle of the current subarray {1,2,3,4} is 2, is the value you are looking for{2}.

让我们再次遵循控制流程，

         *first instance*
         | int binarysearch(int * array, int arrlen, int key ){
         |      ...split the array by middle index and call second instance of the function "binarysearch"
         | }
                
              *second instance*
              | int binarysearch(int * array, int arrlen, int key){
              | ... got the element and return the value to first instance of the function "binarysearch"
              |}

所以你现在可以理解，对于每个自调用，我们都在创建函数的一个实例和 return 一个值（结果或不是结果）当我们得到结果或进入基础条件。

您的代码中也发生了同样的事情：

if(a[mid] < x){
    return binarySearch(a, size, x, mid+1, high);
}
else{
    return binarySearch(a, size, x, low, mid-1);
}

但为了更好地理解它，让我们将 returned 结果的值存储到一个变量中，return 成功（找到密钥时）或失败（当找到密钥时）的变量已达到基本情况，未找到密钥）。

int binarySearch(int a[], int size, int x, int low, int high){
   int result = -1;
   if(low > high) return -1;

   int mid = (low + high)/2;

   if(a[mid] == x){
    return mid;
   }

   if(a[mid] < x){
      result = binarySearch(a, size, x, mid+1, high);
   }
   else{
      result = binarySearch(a, size, x, low, mid-1);
   }
   return result;
}

所以你可以看到我们正在为函数的每个实例创建一个变量 result 并将下一个实例的 returned 值存储到变量中，并继续这样做直到结束(success/failure) 和 return 变量。

return 语句在递归中是如何工作的？

How does the return statement work in recursion?

c++

binary-search