programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Ron McLeod
• Paul Clapham
• Rob Spoor
• Liutauras Vilda
Sheriffs:
• Jeanne Boyarsky
• Junilu Lacar
• Tim Cooke
Saloon Keepers:
• Tim Holloway
• Piet Souris
• Stephan van Hulst
• Tim Moores
• Carey Brown
Bartenders:
• Frits Walraven
• Himai Minh

# Recursion Formula

Ranch Hand
Posts: 79
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
"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
• Number of slices to send:
Optional 'thank-you' note:

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
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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.

M Beck
Ranch Hand
Posts: 323
• Number of slices to send:
Optional 'thank-you' note:
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
• Number of slices to send:
Optional 'thank-you' note:
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
Posts: 13001
66
• Number of slices to send:
Optional 'thank-you' note:
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.