Ufdjrw

250 Floor Tower

Closed-form expression for certain product

Why electric field inside a cavity of a non-conducting sphere not zero?

Is there any references on the tensor product of presentable (1-)categories?

Freedom of speech and where it applies

Yosemite Fire Rings - What to Expect?

What does chmod -u do?

What should you do if you miss a job interview (deliberately)?

Why is it that I can sometimes guess the next note?

Where did Edmond Malone place the Tempest in the chronology of Shakespeare's plays?

Did arcade monitors have same pixel aspect ratio as TV sets?

Is the U.S. Code copyrighted by the Government?

What percentage of fillings performed today are done with mercury amalgam?

Lowest total scrabble score

How can Trident be so inexpensive? Will it orbit Triton or just do a (slow) flyby?

On a tidally locked planet, would time be quantized?

Is it better practice to read straight from sheet music rather than memorize it?

Is it safe to use olive oil to clean the ear wax?

When were female captains banned from Starfleet?

How do I color the graph in datavisualization?

What is the evidence for the "tyranny of the majority problem" in a direct democracy context?

Added a new user on Ubuntu, set password not working?

Symbol used to indicate indivisibility

Can Legal Documents Be Siged In Non-Standard Pen Colors?

Program to generate recursion tree for generic recursive program

What is tail recursion?How to generate a random alpha-numeric string?How do I generate random integers within a specific range in Java?Cycles in family tree softwareC++11 introduced a standardized memory model. What does it mean? And how is it going to affect C++ programming?Image Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionRecursive generators in PHPReplacing a 32-bit loop counter with 64-bit introduces crazy performance deviationsRecursion tree with Fibonacci -Python-Does the C++ standard allow for an uninitialized bool to crash a program?

0

Often when solving a recursive or dynamic programming problem, I find myself drawing a recursion tree to help simplify the question for me. However, for some questions which are complicated I have access to the solution but no idea how to draw the tree.

What I have tried so far is printing out the calling function and it's parameters, and this has proved helpful in some examples. However, I saw this tree for fibonacci(5) here generated by mathematica in this answer: https://mathematica.stackexchange.com/questions/116344/how-do-i-create-a-recursive-tree-plot-for-the-fibonacci-sequence

I was wondering if I could generate the same kind of tree in a mainstream high level language like Python, Java, or C++? The tree could just have the nodes as the function name and parameters like in the image.

java c++ recursion visualization

share|improve this question

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Are you asking how to write a program that generates a tree, or are you asking for an existing such a program?
  
  – Petr
  Mar 7 at 7:45
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Petr If somebody had a program that generates a recursion tree that would be great, I could read the source and figure it out from there. If not, pointers on where to start would be helpful.
  
  – user3586940
  Mar 7 at 7:59
  
  

  
  
  
  

add a comment | 

0

Often when solving a recursive or dynamic programming problem, I find myself drawing a recursion tree to help simplify the question for me. However, for some questions which are complicated I have access to the solution but no idea how to draw the tree.

What I have tried so far is printing out the calling function and it's parameters, and this has proved helpful in some examples. However, I saw this tree for fibonacci(5) here generated by mathematica in this answer: https://mathematica.stackexchange.com/questions/116344/how-do-i-create-a-recursive-tree-plot-for-the-fibonacci-sequence

I was wondering if I could generate the same kind of tree in a mainstream high level language like Python, Java, or C++? The tree could just have the nodes as the function name and parameters like in the image.

java c++ recursion visualization

share|improve this question

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Are you asking how to write a program that generates a tree, or are you asking for an existing such a program?
  
  – Petr
  Mar 7 at 7:45
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @Petr If somebody had a program that generates a recursion tree that would be great, I could read the source and figure it out from there. If not, pointers on where to start would be helpful.
  
  – user3586940
  Mar 7 at 7:59
  
  

  
  
  
  

add a comment | 

Often when solving a recursive or dynamic programming problem, I find myself drawing a recursion tree to help simplify the question for me. However, for some questions which are complicated I have access to the solution but no idea how to draw the tree.

What I have tried so far is printing out the calling function and it's parameters, and this has proved helpful in some examples. However, I saw this tree for fibonacci(5) here generated by mathematica in this answer: https://mathematica.stackexchange.com/questions/116344/how-do-i-create-a-recursive-tree-plot-for-the-fibonacci-sequence

I was wondering if I could generate the same kind of tree in a mainstream high level language like Python, Java, or C++? The tree could just have the nodes as the function name and parameters like in the image.

java c++ recursion visualization

share|improve this question

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

share|improve this question

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

share|improve this question

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

edited Mar 7 at 8:55

c0der

9,26651946

edited Mar 7 at 8:55

c0der

9,26651946

asked Mar 7 at 7:29

user3586940user3586940

1339

asked Mar 7 at 7:29

user3586940user3586940

1339

1 Answer
1

active

oldest

votes

1

Have a look at graphviz and the examples of usage.

Here is an example:

long long fib(int n)

 if (n <= 1) return 1;
 std::cout << "fib" << n << " -> fib" << n-2 << 'n';
 std::cout << "fib" << n << " -> fib" << n-1 << 'n';
 return fib(n-2) + fib(n-1);


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

Running

program > t.dot 
dot -Tpng t.dot

produced:

This is more compact than the requested image, where repeated calls with the same value are represented by one node, and N edges between nodes u,v if there are N calls from fib(u) to fib(v).

To get a tree one has to maintain unique IDs for each call. Here is an example for that:

static unsigned id = 0;
long long fib(int n)

 auto call_id = id++;
 std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
 if (n <= 1) return 1;
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_2 = fib(n-2);
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_1 = fib(n-1);
 return fib_n_minus_2 + fib_n_minus_1;


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

And the graph is:

share|improve this answer

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55038268%2fprogram-to-generate-recursion-tree-for-generic-recursive-program%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

Have a look at graphviz and the examples of usage.

Here is an example:

long long fib(int n)

 if (n <= 1) return 1;
 std::cout << "fib" << n << " -> fib" << n-2 << 'n';
 std::cout << "fib" << n << " -> fib" << n-1 << 'n';
 return fib(n-2) + fib(n-1);


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

Running

program > t.dot 
dot -Tpng t.dot

produced:

This is more compact than the requested image, where repeated calls with the same value are represented by one node, and N edges between nodes u,v if there are N calls from fib(u) to fib(v).

To get a tree one has to maintain unique IDs for each call. Here is an example for that:

static unsigned id = 0;
long long fib(int n)

 auto call_id = id++;
 std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
 if (n <= 1) return 1;
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_2 = fib(n-2);
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_1 = fib(n-1);
 return fib_n_minus_2 + fib_n_minus_1;


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

And the graph is:

share|improve this answer

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

add a comment | 

1

Have a look at graphviz and the examples of usage.

Here is an example:

long long fib(int n)

 if (n <= 1) return 1;
 std::cout << "fib" << n << " -> fib" << n-2 << 'n';
 std::cout << "fib" << n << " -> fib" << n-1 << 'n';
 return fib(n-2) + fib(n-1);


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

Running

program > t.dot 
dot -Tpng t.dot

produced:

This is more compact than the requested image, where repeated calls with the same value are represented by one node, and N edges between nodes u,v if there are N calls from fib(u) to fib(v).

To get a tree one has to maintain unique IDs for each call. Here is an example for that:

static unsigned id = 0;
long long fib(int n)

 auto call_id = id++;
 std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
 if (n <= 1) return 1;
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_2 = fib(n-2);
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_1 = fib(n-1);
 return fib_n_minus_2 + fib_n_minus_1;


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

And the graph is:

share|improve this answer

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

add a comment | 

Have a look at graphviz and the examples of usage.

Here is an example:

long long fib(int n)

 if (n <= 1) return 1;
 std::cout << "fib" << n << " -> fib" << n-2 << 'n';
 std::cout << "fib" << n << " -> fib" << n-1 << 'n';
 return fib(n-2) + fib(n-1);


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

Running

program > t.dot 
dot -Tpng t.dot

produced:

This is more compact than the requested image, where repeated calls with the same value are represented by one node, and N edges between nodes u,v if there are N calls from fib(u) to fib(v).

To get a tree one has to maintain unique IDs for each call. Here is an example for that:

static unsigned id = 0;
long long fib(int n)

 auto call_id = id++;
 std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
 if (n <= 1) return 1;
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_2 = fib(n-2);
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_1 = fib(n-1);
 return fib_n_minus_2 + fib_n_minus_1;


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

And the graph is:

share|improve this answer

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

long long fib(int n)

 if (n <= 1) return 1;
 std::cout << "fib" << n << " -> fib" << n-2 << 'n';
 std::cout << "fib" << n << " -> fib" << n-1 << 'n';
 return fib(n-2) + fib(n-1);


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

program > t.dot 
dot -Tpng t.dot

static unsigned id = 0;
long long fib(int n)

 auto call_id = id++;
 std::cout << "fib" << call_id << " [label="fib(" << n << ")"]n";
 if (n <= 1) return 1;
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_2 = fib(n-2);
 std::cout << "fib" << call_id << " -> fib" << id << 'n';
 auto fib_n_minus_1 = fib(n-1);
 return fib_n_minus_2 + fib_n_minus_1;


int main()

 std::cout << "digraph n";
 fib(5);
 std::cout << "n";

share|improve this answer

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624

answered Mar 7 at 13:13

Michael VekslerMichael Veksler

4,9371624