如何创建一个跟踪来显示存在递归的调用顺序

Question

我想知道递归函数的执行细节。

#include<iostream>
int a=0;
int fac(int n) {
    if (n <= 1)
        return n;
    int temp = fac(n-2) + fac(n - 1);
    a++;
    return temp;
}
int main() {
    fac(4);
    std::cout<<a;
}

输出为4。

我想知道int temp = fac(n-2) + fac(n - 1)；是什么时候执行的，比如fac(4-2)+fac(4-1) -> fac(2)+fac(3)，这时编译器会先完成fac(2)吗？还是一起完成它？我英语不好，希望对你的阅读没有障碍。

Answer 1

完全在算法意义上分析此代码，而不考虑C++实现的复杂性，

                   fac(4)
      fac(2)         +            fac(3)
       |----------------------------|
fac(0) + fac(1)              fac(1) + fac(2)
  1    +   1                    1   + fac(0) + fac(1)
                                    +   1    +   1

如何创建一个跟踪来显示存在递归的调用顺序？

首先，我要指出的是，编译器生成的编译器输出不会与您编写的代码一对一地匹配。编译器根据提供给它的标志应用不同级别的优化，最高级别为-O3，默认级别为-O0，但这些似乎超出了这个问题的范围。创建跟踪会影响此过程本身，因为编译器现在需要满足您对跟踪外观的期望。跟踪实际执行流的唯一真正方法是读取assembly produced by the compiler。

了解了这一点，当执行进入被调用的方法时，我们可以通过打印到屏幕来应用跟踪来查看调用顺序。注意，我删除了a，因为它并不真正跟踪任何东西，只是增加了解释的复杂性。

int fac(int n) {
    std::cout << "fac(" << n << ")" << std::endl;
    if (n <= 1)
        return n;
    int temp = fac(n-2) + fac(n - 1);
    return temp;
}

int main() {
    fac(4);
}

// Output

fac(4)
fac(2)
fac(0)
fac(1)
fac(3)
fac(1)
fac(2)
fac(0)
fac(1)

从我的PC上的输出可以看出，执行是先从左到右深度进行的。我们可以使用此顺序对调用树进行编号，以获得更好的图像。

// Call order

                    1. fac(4)
      2. fac(2)         +         5. fac(3)
          |----------------------------|
3. fac(0) + 4. fac(1)        6. fac(1) + 7. fac(2)
                                       + 8. fac(0) + 9. fac(1)

注意:这并不意味着每个实现的结果都是相同的，也不意味着当您删除跟踪并允许编译器优化时，执行顺序会保持不变，但它演示了递归在计算机编程中是如何工作的。

Answer 2

首先完成fac(2)，然后是fac(1)。输出为4。

调用堆栈将如下所示(从下到上)

                                |---fac(1)
                    |--- fac(2) |
       |---- fac(3) |           |---fac(0)
       |            |
       |            |----fac(1)
       |
fac(4) |
       |
       |            |---- fac(1)
       |---- fac(2) |
                    |---- fac(0)

当n <=为1时，将返回fac()函数