:
: Thanks for your reply Anon, this is helpful.
:
: Do I interpret it correctly by stating that (for i = 4), at the end of
: the first pass in line 38, the following happens:
: a. The value of Number (4) is written to the stack
Yes
: accompanied by an operator (multiplyer) to indicate that
: the numbers have to be multiplied afterwards.
No. The stack is a holding area for values that are added and discarded
as needed. The operator is a part of the function itself and is not
added to the stack. When a function is called, any input parameters it
uses are placed on the stack and it references them as needed. When the
function is done, those values are removed from the stack. A recursive
function call is no different from any other function call.
Think of the stack as a block of memory consisting of 26 individual
locations ('A' to 'Z'). When you first start using the stack, a value is
placed in the next available location ('A' initially, then 'B', then
'C', etc.). When a value is removed from the stack, it is the most
recent value added regardless of what location that is.
When you first call function Factorial(number), the value '4' is placed
onto the stack at position 'A'. Control is then passed to the entry
point for the function which references this value. The variable
'number' is really nothing more than a pointer to that memory location.
The value at that memory location is found to be greater than 1 so a new
value (3) is added to the next position on the stack ('B') and the
function is called again.
Each time the function is called, it looks at the most recent entry
added to the stack. In each case, it is looking at a pointer to a memory
location and so each pass sees a different value. By the 4th pass, the
stack looks like this:
'A' = 4
'B' = 3
'C' = 2
'D' = 1
On the fourth pass, the value in memory location 'D' is determined to be
equal to '1'. The function then removes that value from the stack and
returns the value 1 to what ever process called it. The function does
not know or care that it was a recursive call that it is responding to.
At this point, 'C' is now the top of the stack and execution returns to
the instruction inside the factorial function that takes the returned
value and what it considers to be the value for variable 'number',
multiplies those values together and returns the product.
Eventually, control is returned to the function that initiated this
sequence and the stack is restored to the point it was at before the
Factorial function was first called.
: b. Factorial(Number -1) becomes Factorial(3) with the value 3 as the
: new argument of function Factorial.
: c. Program control returns to beginning of If statement (line 35) to
: check whether the argument of the function Factorial is <= 1 and
: continues the loop until <=1 when it passes by End If.
: d. On the stack, the numbers and operators are excuted and the result
: is returned to the calling location of function Factorial(i) on line
: 27, from where it is displayed.
:
: Thanks,
:
: "_AnonCoward" wrote:
:
: >
: > : > :
: > : I am trying to understand how recursion exactly works.
: > : See example (section) below:
: > : Say i = 4, then Number = 4 during 1st loop. Is Factorial(number -
: > : 1) automatically recognised as a recursive calculation?
: >
: >
: > The reason Factorial is a recursive function is because it calls
: > itself internally. Apart from that, there is nothing special
: > about the function.
: >
: >
: > The expression 'Factorial(number - 1)' is indeed a recursive
: > calculation but nothing special is done by the compiler because
: > of it (at least, not that I'm aware of). As far as the compiler
: > is concerned, it's just another function call.
: >
: >
: > : During the next loop Number = 3. Ultimately 4 x 3 x 2 x 1 has to
: > : be calculated to get the correct answer.
: > : Where are the intermediate values for 4, 3 and 2 stored?
: >
: >
: > On the stack (an area of memory called the stack which is a last-in,
: > first-out queue).
: >
: >
: > Each time a function is called, value types that are passed into the
: > function as parameters are placed onto the stack. The function sees
: > those values as its local variables. When the function exits, the
: > values are removed from the stack.
: >
: >
: > : I don't see
: > : any code for it!It does work, so apparently it is not needed, but
: > : why not? How isit done?
: >
: >
: > Think of it this way - there isn't one invocation of the function
: > Factorial in your example. Instead, the same function is called 4
: > separate times. Each time it's called, there is a separate memory
: > location on the stack that hold the current value of 'number'. Each
: > iteration of the function is unaware of any previous iterations and
: > considers that current value of 'number' to be the relevant value.
: >
: >
: > : Thanks for your explanation,
: > :
: > : Regards,
: > :
: > :
: > : ************************
: > :
: > : Private Sub cmdCalculate_Click(ByVal sender As System.Object, _
: > : ByVal e As System.EventArgs) Handles cmdCalculate.Click
: > :
: > : Dim value As Integer = Convert.ToInt32(txtInput.Text)
: > : Dim i As Integer
: > : Dim output As String
: > :
: > : txtDisplay.Text = ""
: > : For i = 0 To value
: > : txtDisplay.Text &= i & "! = " & Factorial(i) & vbCrLf
: > : Next
: > :
: > : End Sub ' cmdCalculate_Click
: > :
: > : Function Factorial(ByVal number As Long) As Long
: > :
: > : If number <= 1 Then ' base case
: > : Return 1
: > : Else
: > : Return number * Factorial(number - 1)
: > : End If
: > :
: > : End Function ' Factorial
: >
: >
: >
