Win a copy of Cross-Platform Desktop Applications: Using Node, Electron, and NW.js this week in the JavaScript forum!
programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering Languages Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# How to trace recursion questions.

Daniel Gen Li
Ranch Hand
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...

Mike Simmons
Ranch Hand
Posts: 3090
14
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
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: 1563
29
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
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: 1563
29
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
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: 1563
29
By the way, I took a lot of effort to design that....

OP ! i hope that helps you

Greenhorn
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!