c++ - 当同一语句中有两个递归调用时，递归如何工作？

Question

我最近开始研究算法和数据结构。我遇到了斐波那契问题及其使用递归的解决方案。但就是这样。我理解当只有一个时递归调用是如何工作的(比如数字的阶乘)。函数调用不断堆积，直到它们达到基本情况，然后它们开始解开一个所需的答案。

但我不明白的是，当像 f(n)+f(n/2) 这样的表达式中有两个递归调用时，递归是如何工作的。我的意思是先解决哪个调用，何时解决第二个调用。如果将此表达式分配给语句，又如何计算总和？ 我自己写了一个小代码来破译这个。

#include <iostream>
#include <string>


int main()
{
  int recursionTest(int n, char c);
  int x;
  std::cin>>x;
  std::cout<<"Ans:"<<recursionTest(x,'c');

}


int recursionTest(int n,char c)
{
   int result=0;
   if(n==0)
    return 1;
   std::cout<<n<<":"<<c<<std::endl;
   result=recursionTest(n/2,'L')+recursionTest(n/3,'R');////I cant figure 
                                                           out the flow of 
                                                           control here!!!
   return result;
}

我得到了以下输出。

24
24:c
12:L
6:L
3:L
1:L
1:R
2:R
1:L
4:R
2:L
1:L
1:R
8:R
4:L
2:L
1:L
1:R
2:R
1:L
Ans:20

所以我明白了，它是一个树结构。但我仍然不知道我们如何得到 20 作为答案(输入 = 24)。求和表达式是如何工作的，求和是什么，我如何查看树结构并生成相同的输出？

Answer 1

+ 运算符的两个子表达式的求值方式没有定义的顺序。编译器可以发出代码来先评估其中一个，然后再评估另一个。它甚至可以将一侧的某些计算与另一侧的计算交织在一起。例如，它可以计算 n/3，然后是 n/2，然后是右函数调用，最后是左函数调用。

流程控制就像递归的单个案例后跟另一个案例。所以，你的台词:

result=recursionTest(n/2,'L')+recursionTest(n/3,'R');

实际上等同于:

int left = recursionTest(n/2,'L');
int right = recursionTest(n/3,'R');
result = left + right;

除了在我的版本中暗示左边的函数调用保证在右边的函数调用之前被求值。