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

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

How can I create a trace which shows the call order where there is recursion?

首先，我想指出编译器产生的编译器输出不会与您编写的代码一对一匹配。编译器根据提供给它的标志应用不同级别的优化，最高级别是 -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)

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