Somewhere I see a example of recursive method, it works, but I do not understand why.
The method receives an integer and returns the factorial.
The method call itself reducing the original integer value until 0 and then it return 1.
Why the final value received is not 1 if this is the last Retuned value?
Private Function factorial(num as integer) as integer
if num = 0 then
return 1
else
return num * factorial(num-1)
end if
End Function
the caller method
dim i as integer = factorial (TextField1.Text.Val)
MsgBox i.ToText
I can’t find in the documentation how the recursive methods work.
[quote=446411:@Enric Herrera]Somewhere I see a example of recursive method, it works, but I do not understand why.
The method receives an integer and returns the factorial.
The method call itself reducing the original integer value until 0 and then it return 1.
Why the final value received is not 1 if this is the last Retuned value?
Private Function factorial(num as integer) as integer
if num = 0 then
return 1
else
return num * factorial(num-1)
end if
End Function
the caller method
dim i as integer = factorial (TextField1.Text.Val)
MsgBox i.ToText
I can’t find in the documentation how the recursive methods work.[/quote]
When it returns it doesn’t return all the way to the original caller. It returns one level, to where it was called from, which was back to factorial. The actual result is computed by lots of these steps, one after the other:
Thanks Tim, I understand how is the value calculated, the think I do not understand is why Return 1, returns the accumulated value, it’s a convention?
I tried returning any other value in the exit case, and then it doesn’t work.
It might become a bit clearer when you do a little graph. Lets say you calculate the factorial for 3. So you enter the method, and while the abort condition (num = 0) is not true, the method will continue to call itself with a decremented num value:
This makes your code calculate 3 * 2 * 1 *1.
And it makes it clear that every recursive function needs a very definitive exit condition that will always be met to function. Like checking for a negative input value before going into recursion because it would never meet the condition num = 0. At least not before a StackOverflow happens.
To return 1 for an input of 0 is the convention of the factorial method. But it should also work for testing purposes with returning a different value, as long as the result of the recursion is a valid number. Please show your code if it does not.
No, no, the code works, I just would like to understand how, because if I didn’t understood.
Using the debugger we may see that the return, in the else, are no returning nothing because it call itself again, is just when the exit condition is reached that the return is executed but the value returned is not 1, as return 1 seems to say, but it is the accumulate. That is what confused me.
[quote=446415:@Enric Herrera]Thanks Tim, I understand how is the value calculated, the think I do not understand is why Return 1, returns the accumulated value, it’s a convention?
I tried returning any other value in the exit case, and then it doesn’t work.[/quote]
Return 1 doesn’t return the accumulated value. It returns 1 to the previous invocation of factorial (which was in the “else”). On that return, the expression is then calculated and then that returns. As many returns are executed as calls to factorial are made.
So what! The return in the else will return, after the smaller factorial is computed.
No it is not the accumulation. The value return by a return is the expression after the return. The expression which is returned at each step is the factorial of the smaller and smaller number.
Write it out: The returned “1” is only at the very end:
Factorial(5) =
(5 * Factorial(4)) =
(5 * 4 * Factorial(3)) =
(5 * 4 * 3 * Factorial(2)) =
(5 * 4 * 3 * 2 * Factorial(1) =
(5 * 4 * 3 * 2 * 1) = the"1" on this line is the return you are referring to
120
Another way of looking at it is to think about it in reverse:
Factorial(1) returns: 1
Factorial(2) returns: 2 * Factorial(1) = 2 * 1 = 2
Factorial(3) returns 3 * Factorial(2) = 3 * 2 = 6
Factorial(4) returns 4 * Factorial(3) = 4 * 6 = 24
Factorial(5) returns 5 * Factorial(4) = 5 * 24 = 120
Written out descriptively: the “1” value is the answer to Factorial(1) and that answer is returned and fed back to the previous Factorial call, making it part of the calculation for Factorial(2), the result of which is returned for the Factorial(3) calculation and so on and so on until it gets all the way back to the top (i.e. Factorial(57) would have to work its way back through all 57 layers).
The value returned by Factorial is returned to whatever called that function. The “1” is returned to the Factorial(2) function which returns “2” to the Factorial(3) function which returns (6) to the Factorial(4) function and so on and so on until it reaches Factorial(x) which returns its value to the original caller method.
Recursion generally means that you dig yourself a hole deeper and deeper until you reach the condition that doesn’t require recursion (in this case: Factorial(1)=1 with no additional recursion required). Then you climb back out of the hole one step at a time until you’re back where you started.
Factorial(57) causes the Factorial method to call itself recursively 56 layers deep before it finally gets to Factorial(1) which triggers the ending condition–but that value (“1”) is just sent back up one step to get the next value which is sent back one more step to get the next value, and so on all the way up the 56 steps back to the top to get the final answer which is returned to the method that made the original call to the recursive function.