return 语句在递归中是如何工作的?
How does the return statement work in recursion?
#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 语句在此类语句中变得有用。
如果您不从非 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?
好吧,当您指定函数的 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 变量。
#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 语句在此类语句中变得有用。
如果您不从非 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?
好吧,当您指定函数的 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 变量。