c++ - 生成运行时递归调用树的工具

Question

是否有一个简单的工具可以为递归算法生成运行时调用树？比如下面这个计算斐波那契数列的例子:

更具体地说，如果算法是用 C/C++ 实现的呢？

编辑:我想要这棵树来分析递归算法的复杂性。我知道如何生成手头的树。以前我只是在源文件中添加一些“cout”并生成一个点文件并使用graphviz生成树。但我想知道是否有一些好的工具可以节省我编写代码的时间。

编辑:斐波那契数列的示例代码是

//fib.cpp
#include<iostream>
typedef int Int;

Int fib(Int n)
{
  if (n==0)
    return 1;
  else if (n==1)
    return 1;
  else
    return fib(n-2)+fib(n-1);
}

int main()
{
  std::cout<<fib(5)<<std::endl;
  return 0;
}

我已经为这个简单的代码尝试了 valgrind，但找不到如何获取图形。我使用的命令如下:

g++ fib.cpp
valgrind --tool=callgrind ./a.out
kcachegrind callgrind.out.4343

我是错过了一些选项还是什么？

Answer 1

使用 callgrind (cmdline) 然后使用 kcachegrind (gui) 可视化调用树。它是“valgrind”套件中的工具之一。

Callgrind 是一个分析工具，它还允许您查看完整的调用树。您通过在您的程序上运行它来收集分析信息，然后您使用 kcachegrind 分析 callgrind 信息的输出。

附加编辑:不幸的是，正如我刚刚发现的那样，这仅部分适用于递归调用，在这种情况下，递归调用看起来像一个多次调用自身的 stub 。尽管 callgrind 将执行动态调用图，但它在显示传递值和返回值时失败了。静态调用图工具将具有相同的输出(没有调用次数)。

这看起来像这样，而不是你想要的:

我想找出递归函数调用的顺序、参数和返回值的唯一方法是执行回溯(gdb 或 backtrace() 函数)并可视化输出(通过 graphviz)。有一些工具可以做到这一点，但据我所知不是免费提供/开源的。