Results 1 to 9 of 9

Thread: Does VB.Net optimize for tail-end recursion?

Threaded View

  1. #3
    New Member
    Join Date
    Aug 2013
    Posts
    2

    Question Re: Does VB.Net optimize for tail-end recursion?

    Quote Originally Posted by 18experience View Post
    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
  •  



Click Here to Expand Forum to Full Width