Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Recursion - function call trees

 
M. Raven
Greenhorn
Posts: 4
Chrome Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 479
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 4
Chrome Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic