|
-
Aug 12th, 2013, 10:37 AM
#3
New Member
Re: Does VB.Net optimize for tail-end recursion?
 Originally Posted by 18experience
Private Function Fac(ByVal Num As Decimal) As Decimal
'Factorial
If Num = 1 Then
Return 1
Else
Return Num * Fac(Num - 1)
End If
End Function
This function uses tail-end recusion, that is, the last thing it does is recur. It uses:
Return Num * Fac(Num - 1)
instead of
Return Fac(Num - 1) * Num
I have trouble seeing the example as tail recursion. It looks like head recursion, to me. The reason it looks like head recursion is what happens when I rewrite it removing all function chaining. I might be using the term "function chaining" different from what is standard. What I mean by function chaining is the output from a function is used directly as the input to another function. Here is how I rewrote the Fac() without function chaning:
Private Function Fac(ByVal Num As Decimal) As Decimal
'Factorial
If Num = 1 Then
Return 1 Else
Dim Num2 As Decimal = Fac(Num - 1)
Dim RetVal As Decimal = Num * Num2
Return RetVal End If End Function You see that there are statements after the recursive call to Fac(). If there are any computations after a recursive call, I don't think it can be tail recursive. However, I would call it head recursive. Seems to me that head recursion tends to be more frugal on using the stack, and tends to be more compact in coding.
Here is how I would write Fac() using tail recursion and without function chaining:
Private Function Fac(ByVal Num As Decimal, ByVal CumulativeResult As Decimal) As Decimal
'Factorial
If Num = 1 Then
Return CumulativeResult Else
Dim Num2 As Decimal = Num * CumulativeResult
Dim RetVal As Decimal = Fac(Num - 1, Num2)
Return RetVal End If End Function
In this rewritten version, there is no calculation after the recursive call. This is tail recursion. When you need the function's return value to do a calculation, you have to recurse the function first, therefore the calculation will be after, and it is not tail recursive.
And if you like, here is the function rewritten as tail recursive with function chaining:
Private Function Fac(ByVal Num As Decimal, ByVal CumulativeResult As Decimal) As Decimal
'Factorial
If Num = CumulativeResult Then
Return 1 Else
Return Fac(Num - 1, Num * CumulativeResult) End If End Function If I am mistaken, I hope someone will post to explain my error.
Last edited by indinfer; Aug 12th, 2013 at 08:47 PM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|