递归中为何用vector存储递归调用？C++代码解析

一、函数的工作原理 #

我们拿n=3的调用过程拆解，就能清晰看到递归的执行逻辑：

1. 调用printNTimes(3)：创建空的局部vectorarr，因3>0，触发递归调用printNTimes(2)。
2. 调用printNTimes(2)：同样创建空arr，2>0，继续调用printNTimes(1)。
3. 调用printNTimes(1)：创建空arr，1>0，调用printNTimes(0)。
4. 调用printNTimes(0)：创建空arr，此时n=0不满足n>0的条件，直接返回空vector。
5. 回到printNTimes(1)的上下文：把printNTimes(0)返回的空vector赋值给当前arr，执行arr.push_back("Recursion")后，arr包含1个元素，返回该vector。
6. 回到printNTimes(2)的上下文：把printNTimes(1)返回的含1个元素的vector赋值给当前arr，push_back后变成2个元素，返回。
7. 回到printNTimes(3)的上下文：把printNTimes(2)返回的含2个元素的vector赋值给当前arr，push_back后变成3个元素，最终返回包含3个"Recursion"的vector。

二、为什么要将printNTimes(n-1)的返回值存入arr？ #

核心原因是：每一层递归调用都会创建一个全新的局部vectorarr，它们属于不同的函数栈帧，是完全独立的对象。

printNTimes(n-1)返回的是上一层递归生成的、已包含n-1个"Recursion"的vector，当前层的arr初始为空，必须把上一层的结果拿过来，才能在其基础上添加第n个元素。如果省略arr=printNTimes(n-1);这一步，当前层的arr只会是一个仅含1个"Recursion"的vector，最终返回结果永远只有1个元素，完全达不到生成n个元素的目的。

比如去掉赋值语句后，调用printNTimes(3)时，当前arr为空，push_back一次后返回仅1个元素的vector，和预期的3个元素完全不符。

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