• Post Reply Bookmark Topic Watch Topic
  • New Topic

Recursion Formula  RSS feed

 
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Can someone explain how this works?

public static int a (int n)
{
if (n <= 2)
return 1;
else
return a(a(n - 1)) + a (n - a(n - 1));
}
How can the program determine the result here?.
 
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

How can the program determine the result here?.


how does this determine its result? why, exactly the way you've written it.

your "a" is a function that takes an integer parameter, "n", and returns an integer result. if the parameter "n" is less than or equal to 2, then the result is 1. otherwise, the result is —

the function calls itself, several times over even, in order to find its final value. which part of it would you like help understanding?

[edit: clarification]
[ May 03, 2005: Message edited by: M Beck ]
 
Manuel Diaz
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
which part of it would you like help understanding?


return a(a(n - 1)) + a (n - a(n - 1));

I want to know what is "a" for the computer. How can the program use "a" if I have not assigned a value to it.
 
M Beck
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
"a" is the entire function. the computer uses it by calling that function — which in this case happens to mean, the function calls itself.
 
Manuel Diaz
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by M Beck:
"a" is the entire function. the computer uses it by calling that function — which in this case happens to mean, the function calls itself.


Ok, but when I have this a(n-1). How the computers know the result. Im stuck with this. I mean, if the value "n" is 2 for example I know that a(2) is 1 for:

if (n <= 2)
return 1;

But if "n" = 4 how the computer find a(4) if I dont have defined that value like a(2)?
[ May 03, 2005: Message edited by: Manuel Diaz ]
 
M Beck
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
if "n" is <= 2, how does the computer know what the value of a(n) is? well, by calling "a", giving it the value of "n", and seeing what it returns.

same thing for "n" > 2. the computer has the whole definition of "a", and can call the function at any time. for values of "n" > 2, this will involve the function calling itself over again, but you might notice something — whenever "a" calls itself, it does so with a different value of "n", and typically, it will even be a smaller value of "n".

every time "a" calls itself, it will make note of where it was when it called itself — it will keep track of what value it needed, and how far along it had gotten in computing it, when it came to a point of having to call itself.

eventually, it will come down to "n" <= 2, and then the answer is easy. that answer can then be substituted in for the next step up the series, the next step back in the carefully kept records of how and when it called itself. this way, it will compute the final value that you originally asked it for, one bit at a time.

does that make it clearer? if not, perhaps we'll have to examine a different recursive function. your particular function seems a little bit more complicated than what beginners are first introduced to when the notion of recursion comes up — it calls itself more than once per iteration, in a complex tree-recursive pattern. usually, a beginner's first recursive example function is a simpler, more straightforward, usually pure tail-recursive one — i could show you such a one if you think it would help.
 
Manuel Diaz
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i could show you such a one if you think it would help.[/QB]

Well, I understand now, the computers find the values of a(something) until it get to a(2) that is the value it knows. Well, now I understand, but of course, if I can get more examples is better for me, Im pleased to learn more.

THANKS FOR ALL YOUR SUPPORT.
 
M Beck
Ranch Hand
Posts: 323
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you're very welcome, i'm glad i could help!

here, for reference, is a slightly simpler recursive algorithm. this one only calls itself once per turn:

it should be clear what's going on; "factorial 5" will be computed as:

the key being how it "winds up" itself, only to "unwind" afterwards. your function is trickier, because it calls itself more than once per "step" so drawing the picture of its "winding up" would be complicated. but for a really complex recursive function, look to this one:

...yes, i know it's bad style to name a Java method beginning with a capital letter, i really shouldn't do that... but this particular function is named after the mathemathician who invented it, Ackermann, so there's no real way around that capital A.

anyway, Ackermann's function recurses a lot. as in, don't let "x" or "y" become much greater than 10 or so at first, or it will blow up on you! it's a good one for finding out how much recursion one's JVM can survive.
 
Manuel Diaz
Ranch Hand
Posts: 79
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for all again. Actually the last example you gave me (Ackermann) is my next step, but thanks to you, I think I will not have any troubles. I have a few recursive formulas, but I think Ackermann is the harder one. I always get stucked with the first part on a problem (understand it), once I get that, the other comes alone. Ok, no more writing, I dont want to bore you anymore, thanks a lot.
[ May 03, 2005: Message edited by: Manuel Diaz ]
 
lowercase baba
Bartender
Posts: 12565
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
as a side note, this is a good example of why it is important to use good names for functions (and variables).

using "a" as a function name tells you nothing about said function, and can (in this case, did) lead to confusion. using a function name of "myFunction" or some such might have helped clarify the issue...



here, you can more easily see the funtion calls itself.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!