Ex 20-2 Recursive calls

zavodney · August 25th, 2011, 08:55 PM

I don't understand why your function works. Once 'value' gets to 1 the function should return '1' according to your 'if (value <= 1) then return 1' line. I don't see why 'value' is being decremented when it is not being set. Your code is:

Code:

    Private Function Factorial(ByVal value As Long) As Long
        If (value <= 1) Then Return 1
        Return value * Factorial(value - 1)
    End Function

To see what was happening I changed it to this:

Code:

    Private Function Factorial(ByVal value As Long) As Long
        Console.WriteLine("value in: " & value)
        If (value <= 1) Then Return 1
        interim = value * Factorial(value - 1)
        Console.WriteLine("interim = " & interim)
        Return interim
        ' Return value * Factorial(value - 1)
    End Function

My output was:
value in: 5
value in: 4
value in: 3
value in: 2
value in: 1
interim = 2
interim = 6
interim = 24
interim = 120
answer = 120 (returned to calling routine)

How was 'value' being decremented and why was it decremented to 1 before the 'interim' value was calculated? I understand the first recursive call giving me the 'value = 5' and 'value = 4'. Obviously it looped and when it finished looping it returned the final value of 'interim' but why did it loop and only return 1 answer?

zavodney · August 25th, 2011, 11:19 PM

Ok, I see why it calls itself and why 'value' keeps decrementing. I still need to ask why 'If (value <= 1) Then Return 1' doesn't return the value of '1'?

Rod Stephens · August 26th, 2011, 10:16 AM

The parameter value is a parameter not a variable inside the function so it's the function call that creates it. The value itself isn't really decremented. Instead a new parameter is created that has is equal to value - 1 and that's passed to the next call in the chain.

For example, if your code calls Factorial(5), then that code evaluates 5 * Factorial(4). The call to Factorial(4) evaluates 4 * Factorial(3), and so on.

Eventually you get to Factorial(1). At that point, the code returns 1. You can see the input value 1 in your WriteLine statements. (Good use of those, by the way.) You don't see 1 as an interim value because when value is 1, the code doesn't get to that WriteLine statement.

The end result is:

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 = 120

I hope that helps. Recursion is very unnatural and can be very confusing. And this is about the simplest example possible with one function calling itself directly. Other recursive programs use multiple functions that call each other in complex ways or that call themselves multiple times. Then things can be really confusing.

For some interesting examples, see:

Draw a fractal Hilbert curve in VB.NET
http://www.vb-helper.com/howto_net_f...ert_curve.html
This one is multiply recursive--a routine calls itself multiple times.

Draw a Sierpinski fractal curve in C#
http://blog.csharphelper.com/2009/12...urve-in-c.aspx
This one is multiply indirectly recursive--four routines call each other multiple times. (I need to make a VB version of this one. I thought I had one.)

zavodney · August 26th, 2011, 10:34 AM

I think I understand ... the returns during the recursive calls are returned to the function which ignores them while the final return is made to the initial calling routine. This provides the final and correct answer. btw, I definately like the console.writeline over messageboxes for something like this.

Rod Stephens · August 26th, 2011, 11:00 AM

Well it doesn't ignore them, it just saves the result, multiplies by a number, and then returns that. You could rewrite the function like this:

Code:

Private Function Factorial(ByVal value As Long) As Long
    Dim result As Long
    If (value <= 1) Then
        result = 1
    Else
        Dim value_minus_1 As Long = Factorial(value - 1)
        result = value * value_minus_1
    End If
    Return result
End Function

I definately like the console.writeline over messageboxes for something like this.

Yes. It's also really handy when you're trying to debug graphics code. For example, if you put a breakpoint in a Paint event handler or display a MessageBox there, it interferes with the code.

zavodney · August 26th, 2011, 09:48 PM

Thank you for your explanations.

Keith Z.