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

Question

我用 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;
    }

}

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

Answer 1

任何不返回任何内容的函数 (void) 必须在用完要执行的操作之前遇到 return 语句。这很简单，因为没有神奇的“如果我不返回某物就返回 X”命令，使用该函数的人可能依赖于您 promise 的返回(但未能交付)。

如果您现在沿着导致原始函数中的那些递归调用的路径前进，您将看到最初启动递归调用的调用现在必须返回一些东西。相反，它只是简单地忽略递归调用的结果并用完所有事情。

这会导致称为未定义行为 的事情，因为 C++ 根本不知道您希望它做什么。事实上，"it is legal for it to make demons fly out of your nose." ，虽然它通常会 - 出于其灵魂的纯粹仁慈 - 将自己限制在可怕和不可预测的崩溃中。

为什么您看不到差异，存在两个主要选项:

• 代码的编译方式使其未定义性将按预期工作。您绝不能永远不要依赖它。实际上，您的代码将以单个寄存器保存您的返回值(RAX)的方式进行编译。由于递归调用是您的代码所做的最后一件事，因此该寄存器可能不会再次被修改，从而导致代码表现得就好像您已经返回了递归调用的结果.

• 您的测试用例实际上从不进行递归调用。这在技术上是合法的，因为程序的正确性取决于它在运行时的行为。您也不应该依赖于此。

如果你有兴趣，标准的相关部分是 [stmt.return]/2，它说:

[...] Flowing off the end of a function is equivalent to a return with no value; this results in undefined behavior in a value-returning function.

“流动”是指控制流，“返回值函数”是指返回类型不是 void 的任何函数。