递归中return语句的运行机制是什么？结合二分查找递归实现的疑问

你给出的递归实现二分查找的C++代码如下：

#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);
}

接下来针对你的疑问逐一解答：

1. 不写递归调用前的return会产生什么差异？ #

C++标准明确规定：返回值类型非void的函数，如果某条执行路径结束时没有执行return语句，属于未定义行为。
实际运行时的差异可以分为两种场景：

• 极端巧合的场景：内层递归调用的返回值刚好存储在用来传递返回值的寄存器（比如x86架构下的eax寄存器）中，且后续没有其他操作覆盖这个值，此时即使没写return，上层调用方也会碰巧拿到正确的返回值，看起来运行结果和加了return没有区别。
• 绝大多数场景：函数执行到路径末尾没有主动return，会返回寄存器中残留的随机脏值，程序输出错误结果，甚至直接触发崩溃。

2. 内部运行逻辑是否会发生变化？ #

运行逻辑的差异是明确的：

• 加了return的情况：内层binarySearch调用执行完成得到结果后，会被当前函数主动返回给上层调用方，层层传递直到最外层的main函数，整个返回链路是完全可控的。
• 没加return的情况：内层binarySearch的递归调用流程本身不会中断，还是会完整执行到结束，但是调用得到的结果会被直接丢弃，当前函数没有向上层调用方返回有效数值，上层拿到的是不确定的垃圾值。

3. 递归场景下return语句什么时候是必要的？ #

只要同时满足以下两个条件，return语句就是必须要写的：

• 递归函数本身的返回值类型不是void，需要向上层返回结果
• 当前执行路径需要把内层递归调用得到的结果传递给上层调用方

简单来说，递归调用本质就是函数调用自身，你调用其他有返回值的普通函数需要把结果return给上层的时候，调用递归函数也同样需要加return。

内容的提问来源于stack exchange，提问作者Karmveer Singh