File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes How to trace recursion questions. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of EJB 3 in Action this week in the EJB and other Java EE Technologies forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "How to trace recursion questions." Watch "How to trace recursion questions." New topic
Author

How to trace recursion questions.

Daniel Gen Li
Ranch Hand

Joined: Jan 02, 2010
Posts: 32
For a question like this:


The problem may ask something like what this code will output if you call doSomething(5).

I'm learning recursion right now, and I find it really hard tracing the execution of these questions. Are there any techniques on doing these questions? Because I'm looking at some of these questions on previous AP exams and it takes me around 5 mins just to do one and I sometimes get lost on which recursive call I'm at. Especially the ones that made more than recursive call, they are really confusing. I usually don't have this much trouble with programming...

any help is greatly appreciated...


Li
Mike Simmons
Ranch Hand

Joined: Mar 05, 2008
Posts: 2969
    
    9
Well, for this particular problem, you might try looking at it from the other direction. That is, you can see that it starts with doSomething(5) , then calls doSomething(4), then doSometing(3) etc down to doSomething(0). Try looking at those in the reverse order.

What does doSomething(0) do?

What does doSomething(1) do?

What does doSomething(2) do?

And so on.

A pattern should start to emerge. Such patterns can be much easier to understand if you start with small parts of the pattern, before trying to understand the whole thing.
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

I've also just printed out execution traces, increasing the indent each level:In the end it's the same thing as what Mike's saying, but indent-ier.

And if you turn the output on its side it's a graph of how awesome it is.
salvin francis
Ranch Hand

Joined: Jan 12, 2009
Posts: 917

hi David Newton

You have probably printed out the execution trace of a different program(than the OP) here.
Also I do feel that it will be difficult to show in text the execution of



since it contains two recursive calls to same functions before and after a line of code.


do correct me if i am wrong:

n=3



My Website: [Salvin.in] Cool your mind:[Salvin.in/painting] My Sally:[Salvin.in/sally]
David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

salvin francis wrote:You have probably printed out the execution trace of a different program(than the OP) here.

Well, yes, a factorial. Otherwise I'd be giving away too much specific info.
lso I do feel that it will be difficult to show in text the execution of [...]

I agree it's more complicated, but for people that are more visual, it can be really helpful. It took me these kinds of traces, along with some boxes to indicate nesting, to understand how recursion works. Not everybody might need such a tool, or it may be more confusing than helpful for some.To me, that's pretty noisy, but if I read it line-by-line, and I include a reference tree of the graph, I'm usually all set.

(And you'll notice my implementation is a little "backwards"
salvin francis
Ranch Hand

Joined: Jan 12, 2009
Posts: 917

This gives a better idea

To be honest, I wasnt able to understand that output at all !!!
how do you make sense of such gibbrish !!


David Newton
Author
Rancher

Joined: Sep 29, 2008
Posts: 12617

Once there are boxes around the levels it's the same thing. It would have been just as easy to create GraphViz output (or whatever) to get a pretty picture :)
salvin francis
Ranch Hand

Joined: Jan 12, 2009
Posts: 917

By the way, I took a lot of effort to design that....

OP ! i hope that helps you
Chester Saddlemeyer
Greenhorn

Joined: Feb 13, 2014
Posts: 1
David Newton wrote:I've also just printed out execution traces, increasing the indent each level:In the end it's the same thing as what Mike's saying, but indent-ier.

And if you turn the output on its side it's a graph of how awesome it is.


Hi David, I've been searching for a way to do exactly this! And for a factorial function, no less :)

http://stackoverflow.com/questions/21748322/how-to-print-a-recursive-trace-factorial-function

How exactly did you position your print statements to achieve that lovely return trace? The placement is eluding me...

Thanks for any help!

 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: How to trace recursion questions.
 
Similar Threads
What does recursion code hurt ?
multiple recursion and stacks
Timing Methods
Recursion Reciprocals
While not running out.