A tool for creating a recursive runtime call tree

Question

Is there a simple tool to create a runtime call tree for a recursive algorithm? For example, to calculate the Fibonacci number:

More specifically, 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 a tree in my hand. I used to just add some “cout” to the soure file and generate a dot file and use graphviz to generate the tree. But I want to know if there are any good tools, so I can save time writing code.

EDIT: Code Example for Fibonacci Number

//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 tried valgrind for this simple code but cannot find how to get the graph. The command I used is as follows:

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

?

Answer 1

callgrind (cmdline), kcachegrind (gui), . "valgrind".

Callgrind - , . , , callgrind kcachegrind.

: , , , , . , callgrind , , . callgraph ( ).

, , :

, , , backtrace (gdb backtrace()) ( graphviz). , , / .

Answer 2

, , ( , . node :

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

, :

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

:

node* tree;
fibo( 5, tree );

, .

Answer 3

.

Answer 4

" "? - ?

If you want to get a list of all the calls at runtime, you can simply create these functions and print something in each of them (or add to the vector or something else), for example:

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 get something like this, 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 calculated at compile time, so all function calls will be expanded, and the constants will be collapsed, which will lead to a code that will be evaluated in constant time.