在递归函数中返回函数和不返回有什么区别？

我用C++写了一个简单的二进制搜索函数。代码如下所示：在递归函数中返回函数和不返回有什么区别？

int binary_search(int arr[], int key, int imin, int imax) 
{ 
    if (imin > imax) 
    { 
     return -1; 
    } 
    else 
    { 
     int imid = imin + (imax - imin)/2; 
     if (arr[imid] > key) binary_search(arr, key, imin, imid - 1); 
     else if (arr[imid] < key) binary_search(arr, key, imid + 1, imax); 
     else return imid; 
    } 

}

但我发现，如果我在第10行和11加return，代码似乎以同样的方式工作。代码如下：

int binary_search(int arr[], int key, int imin, int imax) 
{ 
    if (imin > imax) 
    { 
     return -1; 
    } 
    else 
    { 
     int imid = imin + (imax - imin)/2; 
     if (arr[imid] > key) return binary_search(arr, key, imin, imid - 1); 
     else if (arr[imid] < key) return binary_search(arr, key, imid + 1, imax); 
     else return imid; 
    } 

}

所以我的问题是这两种情况有什么区别？

来源

2015-09-20 Xiang Zhang

打开更多编译器警告。你应该得到一个关于达到非void函数的结尾。 – Biffen

您是否检查过返回值的正确性？ –

任何不会返回任何内容的函数（void）在用完之前都必须遇到return声明。这很简单，因为没有魔法“如果我不返回某些东西就会返回X”，而且该人使用函数可能依赖于您承诺的回报（但未能交付）。

如果您现在按照导致原始函数中的递归调用的路径，您将看到现在首先启动递归调用的调用必须返回一些内容。相反，它简单地忽略了递归调用的结果并且耗尽了要做的事情。

这导致了一种叫做未定义的行为，因为C++不知道你期望它做什么。实际上，"it is legal for it to make demons fly out of your nose."虽然通常会脱离其灵魂的纯仁 - 但却限制了它的崩溃，可怕和不可预测。

两个主要选项存在，为什么你没有看到一个区别：

的代码是这样一种方式，如预期其不确定的烦躁将工作编译。你必须不依赖于此，永远。在实践中，您的代码将被编译为一个寄存器保存您的返回值（RAX）。由于递归调用是您的代码最后一件事，因此该寄存器可能不会再次被修改，导致代码执行，就好像您已经返回了递归调用的结果。

你的测试用例从来没有真正做过递归调用。这在技术上是合法的，因为程序的正确性取决于它在运行时的行为。你应该也不依靠这个。

如果你有兴趣，该标准的相关部分[stmt.return]/2，其中说：

[...]流下的函数到底是相当于到没有价值的回报;这会导致值返回函数中的未定义行为。

“流动”是指控制流程，“价值返回功能”是具有除void以外的返回类型的任何功能。

来源

2015-09-20 10:38:09

请注意，'main'是一个异常，并会返回'0'。 – Jarod42

@ Jarod42是的，但在另一种意义上它也是一个例外，因为无论如何你可能不会调用'main'！ –

如果返回非void一个函数“落入端的”（即没有返回语句）和呼叫者使用的返回值，则结果是不确定的行为。这种情况发生在你的第一个版本中（无论是递归调用还是调用者），除非 - 偶然 - 你的测试用例只会导致执行return imid语句。

不幸的是，未定义行为的一个可能结果是代码似乎对所有测试用例都正常工作。没有什么可以阻止这一点。程序崩溃（或其他异常程序终止）是人们在未定义行为发生时经常更熟悉的，但未定义行为的更隐蔽的结果是代码似乎的行为就像没有任何错误一样。

在实践中，您的第一个案例似乎正确工作的原因是盲目的运气。由于历史原因，我不会详细介绍，一些公平的编译器会将用于计算的工作数据（即函数中的语句）和结果放入机器寄存器中，不会打扰清除这些寄存器，并且（当函数返回int或其他非struct类型）使用那些相同的机器寄存器来保存函数的返回值。所以你可以很幸运，第一个例子中的代码就像第二个代码一样。然而，问题在于标准没有保证这种行为，在编译器之间可能会改变，可能会随编译器设置（例如优化选项）而改变，甚至在将来某个时候编译器升级时甚至可能会改变。

来源

2015-09-20 10:49:48 Peter

递归最终将通过实际执行return语句结束。此时，编译器会将返回值放在用于返回值的位置。

当你回到调用函数，不执行任何其他的返回语句，它恰好仍然存在。只是偶然。

来源

2015-09-20 10:58:53

在递归函数中返回函数和不返回有什么区别？

回答

相关问题