一种生成运行时递归调用树的工具

Question

是否有一个简单的工具来为递归算法生成运行时调用树？如下面的计算Fibonacci数:

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

编辑:我希望这棵树分析递归算法的复杂性.我知道如何生成树.以前我只是在soure文件中添加一些"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信息的输出.

附加编辑:不幸的是,因为我刚刚发现这将仅部分用于递归调用,在这种情况下看起来像一个存根调用自身多次.即使callgrind将执行动态调用图,它也会在此处显示传递和返回的值.静态调用图工具将具有相同的输出(没有调用的次数).

这将是这样的,而不是你想要的:

我想找出哪个序列以及调用递归函数的参数和返回值的唯一方法是进行回溯(gdb或backtrace()函数)并可视化该输出(通过graphviz).有工具,但据我所知,不是免费提供/开源.

Answer 2

您可以实现一棵树并存储对活动叶子的引用。