Win a copy of Re-engineering Legacy Software this week in the Refactoring forum
or Docker in Action in the Cloud/Virtualization forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

How to trace recursion questions.

 
Daniel Gen Li
Ranch Hand
Posts: 32
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
Mike Simmons
Ranch Hand
Posts: 3028
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1263
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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

 
David Newton
Author
Rancher
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1263
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12617
IntelliJ IDE Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Bartender
Posts: 1263
10
Eclipse IDE Google Web Toolkit Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
By the way, I took a lot of effort to design that....

OP ! i hope that helps you
 
Chester Saddlemeyer
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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!

 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic