aspose file tools*
The moose likes Beginning Java and the fly likes Recursion - function call trees Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of The Java EE 7 Tutorial Volume 1 or Volume 2 this week in the Java EE forum
or jQuery UI in Action in the JavaScript forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Recursion - function call trees" Watch "Recursion - function call trees" New topic
Author

Recursion - function call trees

M. Raven
Greenhorn

Joined: Sep 23, 2011
Posts: 4

I am wondering how I can trace through a program that has multiple recursive calls, such as the one below, and find out the return value :

for n like 5 or 6. No matter how I try I can't figure this out
Ralph Cook
Ranch Hand

Joined: May 29, 2005
Posts: 479
One way is to treat the function call as returning a single value; we know that it does that by invoking a method, but we can ignore that momentarily while we reason through things.

ex234(5) ends up as ex234(2) + 5 + ex234(3) + 5

Now we can determine the value returned by each of those

ex234(2) ends up as ex234(-1) + 2 + ex234(0) + 2
ex234(3) ends up as ex234(0) + 3 + ex234(1) + 3

We know that each of the ex234(0) and ex234(less than 0) end up as empty strings. That leaves us with

ex234(1) as ex234(-2) + 1 + ex234(-1) + 1 => "" + 1 + "" + 1 => "11"

So this gives us

ex234(3) as "" + 3 + "11" + 3 => "3113"
ex234(2) as "" + 2 + "" + 2 => "22"

and now we can substitute back into the first expression

ex234(5) as "22" + 5 + "3113" + 5 => "22531135"

I hope that's right; I haven't run the code...

rc
M. Raven
Greenhorn

Joined: Sep 23, 2011
Posts: 4

That gives the correct result for 5
I'll have a go at this for 6 and try to understand what's going on better. Thank you for your help.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Recursion - function call trees