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 all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Bear Bibeault
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
Sheriffs:
• Knute Snortum
• Junilu Lacar
• paul wheaton
Saloon Keepers:
• Ganesh Patekar
• Frits Walraven
• Tim Moores
• Ron McLeod
• Carey Brown
Bartenders:
• Stephan van Hulst
• salvin francis
• Tim Holloway

# Another recursion question

Ranch Hand
Posts: 543
4
Hi guys I'm just wondering why and how come this code works

the thing I'm confused with is so lets just say we enter the value 5 in as the param for the method fact won't it not just return 5 * fact(5-1) I thought when we use the return keyword control is returned to the calling method so in this case why wouldn't return be controlled back to main with the result of 5 * fact(5 - 1)??? what is return doing in this case?

thanks

Bartender
Posts: 634
9
Well, that's exactly what it does return. But first it must compute fact(5-1) and then multiply that by 5. So what you think fact(5-1) will return?

Ranch Hand
Posts: 543
4

Fred Kleinschmidt wrote:Well, that's exactly what it does return. But first it must compute fact(5-1) and then multiply that by 5. So what you think fact(5-1) will return?

hey Fred thanks for the reply honestly I'm not too sure what it will return,I'm guessing it would returns fact(4-1)?

Fred Kleinschmidt
Bartender
Posts: 634
9
Not quite. It returns (4 * fact(4-1)). And what will fact(4-1) return? And fact(3-1)? And fact(2-1)? This is what recursion is all about.

Ranch Hand
Posts: 543
4

Fred Kleinschmidt wrote:Not quite. It returns (4 * fact(4-1)). And what will fact(4-1) return? And fact(3-1)? And fact(2-1)? This is what recursion is all about.

ohh ok thanks Fred,another thing that is confusing me and which is hard to explain in words,is the return state getting executed twice I mean for example lets say at the start of the code when we enter fact(5) it calls the function fact with 5 as the parameter and in the function it eventually comes to the return statement well that return statement is executed then the recursive function calls are placed on the stack now when it unwinds and gets back down to the stack "block" which is fact(5) it must call the return statement again in order to actually return the answer which is 120 to the main function,

I hope that makes sense.

Fred Kleinschmidt
Bartender
Posts: 634
9
Try working it out by hand.
When you call fact(5), it gets to the line
Now before multiplying by 5, it must compute fact(4), which gets to the line that becomes
Niow before multiplying by 4, it must compute fact(3), which gets to the line that will be
Now before multiplying by 3, it must compute fact(2), which gets to the line
Before multiplying by 2, it must compute fact(1), which gets to the line
So fact(1) is 1, so fact(2) becomes 2 * fact(1) or 2 * 1.
And fact(3) has resolved to 3 * fact(2) or 3 * 2 * 1.
and fact(4) therefore resolves to 4 * fact(3), or 4 * 3 * 2 * 1
and finally fact(5) resolves to 5 * fact(4), or 5 * 4 * 3 * 2 * 1

Ranch Hand
Posts: 543
4

Fred Kleinschmidt wrote:Try working it out by hand.
When you call fact(5), it gets to the line
Now before multiplying by 5, it must compute fact(4), which gets to the line that becomes
Niow before multiplying by 4, it must compute fact(3), which gets to the line that will be
Now before multiplying by 3, it must compute fact(2), which gets to the line
Before multiplying by 2, it must compute fact(1), which gets to the line
So fact(1) is 1, so fact(2) becomes 2 * fact(1) or 2 * 1.
And fact(3) has resolved to 3 * fact(2) or 3 * 2 * 1.
and fact(4) therefore resolves to 4 * fact(3), or 4 * 3 * 2 * 1
and finally fact(5) resolves to 5 * fact(4), or 5 * 4 * 3 * 2 * 1

Thanks Fred I understand how that part of recursion works but great explanation easy to follow =)

but the part I'm confused with is the return keyword when it comes this example of recursion isn't the lines with the return statement essentially running twice?

thanks for sticking with me =)

author
Posts: 23811
140

but the part I'm confused with is the return keyword when it comes this example of recursion isn't the lines with the return statement essentially running twice?

It is actually more than twice. Following the example, you can see that the main() method is calling the fact() method, which is then calling the fact() method, which is then calling the fact() method, which is then calling the fact() method, and again, which is then calling the fact() method. At this point, you are five method calls deep -- so, you will need five return statements to get back to the main() method.

Henry

Fred Kleinschmidt
Bartender
Posts: 634
9
• 2
lets look at the line
when x=2
so that becomes
Now we know that fact(1) returns 1, so the above line of code becomes
Now that value of 2 is returned to the code that called when x was 3, so that line becomes
And so on.

Ranch Hand
Posts: 543
4

Fred Kleinschmidt wrote:lets look at the line
when x=2
so that becomes
Now we know that fact(1) returns 1, so the above line of code becomes
Now that value of 2 is returned to the code that called when x was 3, so that line becomes
And so on.

Thanks Fred much appreciated =)

Marshal
Posts: 61691
193
• 1

You can shorten and neaten that code. Let's start by getting rid of the excess whitespace, which does nothing for legibility:-Now let's have the proper names for the class and method:-The old C books teach you how to squeeze all the code together and use short names, but there has been forty years' improvement in memory since then, so there is no need to write fact which is a real wo‍rd instead of factorial. Also, I don't like to squeeze else and two braces all onto one line, but I won't change that here. I shall however add spaces around the braces, which shou‍ld be separated from the rest of the code.
You can shorten the main method because you are only using result once. Also more spaces after if and around −.Now, you can neaten the double return with the :? operator. The ?: operator is very useful for shortening code like that but it does take a bit of getting used to.Finally: I am going to change the base case. The mathematicians will tell you that 1! is not defined. They will tell you that only 0! is defined, so I think the base case is slightly different.Of course you now have one more level of recursion.

Master Rancher
Posts: 3001
105
• 1
And add a check that the argument is not negative.