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.
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.
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.
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 ]
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.
There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
I'm not dead! I feel happy! I'd like to go for a walk! I'll even read a tiny ad: