递归求数组最大值代码执行逻辑疑问求助

这是《Grokking Algorithms》中用于练习函数式编程、递归及分治（D&C）思想的求数组最大值代码。我疑惑的是函数底部的return语句何时执行，每次执行到sub_max = max(arr)时就回到函数开头，不清楚该return语句的执行时机，恳请解答！

#include <iostream>
#include <vector>
#include <stdexcept>

using std::cout;
using std::endl;

template <typename T>
T max(std::vector<T> arr) {
    if (arr.empty()) throw std::invalid_argument("Cannot select max value from empty sequence");
    if (arr.size() == 1) return arr.at(0);

    T back = arr.back();
    arr.pop_back();

    T sub_max = max(arr);
    
    return back > sub_max ? back : sub_max; 
}

int main() {
    std::vector<int> array = {1, 5, 10, 25, 16, 1};
    cout << max(array) << endl;

    std::vector<int> negative_array = {-1, -5, -10, -25, -16};
    cout << max(negative_array) << endl;
}

核心逻辑：递归的「递」与「归」 #

递归函数的执行分为两个明确阶段：递（向下拆解调用）和归（向上计算返回）。你看到的「执行到sub_max = max(arr)就回到函数开头」是递的阶段，而底部的return语句要等到归的阶段才会执行——也就是当当前层触发的递归调用完成并返回结果后，才会回到当前函数继续执行后续代码。

我们拿第一个测试数组{1,5,10,25,16,1}做具体拆解：

1. 递的阶段：逐层拆解问题 #

• 第1次调用：max({1,5,10,25,16,1})，数组长度≠1，取出末尾元素1，调用max({1,5,10,25,16})
• 第2次调用：max({1,5,10,25,16})，长度≠1，取出16，调用max({1,5,10,25})
• 第3次调用：max({1,5,10,25})，长度≠1，取出25，调用max({1,5,10})
• 第4次调用：max({1,5,10})，长度≠1，取出10，调用max({1,5})
• 第5次调用：max({1,5})，长度≠1，取出5，调用max({1})
• 第6次调用：max({1})，长度=1，触发终止条件，直接返回1，这是整个递归链的终点。

2. 归的阶段：逐层计算返回 #

从最底层的递归调用开始往回走，每一层都会执行底部的return语句：

• 回到第5次调用：sub_max = 1，执行return 5 > 1 ? 5 : 1，返回5
• 回到第4次调用：sub_max =5，执行return 10 >5 ?10:5，返回10
• 回到第3次调用：sub_max=10，执行return25>10?25:10，返回25
• 回到第2次调用：sub_max=25，执行return16>25?16:25，返回25
• 回到第1次调用：sub_max=25，执行return1>25?1:25，返回25，最终输出结果。

关键结论 #

• 底部的return语句不会在递的阶段执行，只有当当前层的递归调用完成并返回结果后，才会执行该行代码，把当前层的计算结果返回给上一层调用者。
• 递归终止条件（arr.size()==1时的return）是整个递归链的「起点」，所有后续的return都是基于这个终止点的结果逐层向上计算而来。

内容的提问来源于stack exchange，提问作者Ahmed Salah