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?
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.
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
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?
Fred Kleinschmidt wrote:lets look at the line
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.
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 word 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 should be separated from the rest of the code.
Adam Chalkley wrote:. . .