• Post Reply Bookmark Topic Watch Topic
  • New Topic

Another recursion question  RSS feed

 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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





 
Fred Kleinschmidt
Bartender
Posts: 529
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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?
 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 529
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 529
9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 =)
 
Henry Wong
author
Sheriff
Posts: 23188
124
C++ Chrome Eclipse IDE Firefox Browser Java jQuery Linux VI Editor Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adam Chalkley wrote:
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: 529
9
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 =)
 
Campbell Ritchie
Sheriff
Posts: 54495
150
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Adam Chalkley wrote:. . .
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.
 
Piet Souris
Rancher
Posts: 1885
64
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
And add a check that the argument is not negative.
 
Adam Chalkley
Ranch Hand
Posts: 257
1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks for the tips Campbell =)
 
Campbell Ritchie
Sheriff
Posts: 54495
150
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
That's a pleasure
 
Don't get me started about those stupid light bulbs.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!