A tool to generate run time recursive call tree

Is there an easy tool to generate run time call tree for a recursive algorithm? Such as the following one for computing Fibonacci number :

More specificly,what if the algorithm is implemented in C/C++?

EDIT:I want this tree to analyze the complexity of a recursive algorithm.I know how to generate the tree in hand. Previously I just add some "cout" in soure file and generate a dot file and use graphviz to generate the tree.But I want to know if there was some good tools开发者_运维技巧 so I can save my time of writing the code.

EDIT:An example code for Fibonacci number is

//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;
}

I have tried valgrind for this simple code but can't find how to get the graph.The command I used is as follow:

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

Did I miss some options or what ?

Use callgrind (cmdline) and then kcachegrind (gui) to visualize call trees. It's one of the tools from the 'valgrind' suite.

Callgrind is a profiling tool which also allows you to see the complete call tree. You collect the profiling info by running it on your program, then you analyze the output of the callgrind info with kcachegrind.

Additional edit: Unfortunately as i just found out this will work only partially for recursive calls which will in this case look like a stub calling itself multiple times. Even though callgrind will do a dynamic call graph it fails here at showing the passed and returned values. A static callgraph tool will have the same output (without the amount of times called).

This will look like this, not what you want:

I guess the only way to find out in which sequence and with which parameters and return values the recursive function has been called is to do a backtrace (gdb or the backtrace() function) and visualize that output (via graphviz). There are tools for that but as far as i know not freely available/open source.

I don't think there is a tool as such, but you can manually create the tree (and then print it however you like it. For that particular algorithm, a tree node would be something like:

struct node {
   int value;
   int result;
   node *left;
   node *right;
   node( int value ) : value(value), result(), left(), right() {}
};

And then you can modify the function to allow it to construct the tree:

int fibo( int value, node*& ptr )
{
   ptr = new node( value );
   ptr->result = fibo( value-1, ptr->left ) + fibo( value-2, ptr->right );
   return ptr->result;
}

Intially call it like:

node* tree;
fibo( 5, tree );

And then work on the tree that you have built.

You can implement a tree and store a reference to the active leaf.

What do you mean by "obtain run time call tree"? You want to obtain a list of calls in some array?

If you want to get a list of all calls at runtime, you can simply create those functions and print something in each of them (or add to a vector or whatever), e.g:

int fib(int i) {
  int ret;
  printf("fib(%d)\n",i);
  if (i>2) ret=fib(i-2)+fib(i-1);
  else ret=i;
  printf("fib-end(%d)\n",i);
}

If you want to obtain something similar but at compile time, you can try the following approach:

template <int i>
inline int fib() {
  //do something
  return fib<i-2>()+fib<i-1>();
}

template <>
inline int fib<0>() {return 0;}

tempalte <>
inline int fib<1>() {return 1;}

In the latter case, the fibonacci number will be computed at compile-time, so all function calls will be expanded and constants collapsed, resulting in a code that will evaluate in constant time.