Does VB.Net optimize for tail-end recursion?

[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

Because both would give you the same answer, but I know that some languages (Scheme, for instance) optimize tail-end recursion. So, if you can help it, recurring is the last thing you should do, and you code will fun faster.

Does anyone know if VB does this?

[circuits2]

I don't think it matters in VB. I found this example on MSDN:

Function Factorial(ByVal N As Integer) As Integer
   If N <= 1 Then      ' Reached end of recursive calls.
      Return 1         ' N = 0 or 1, so climb back out of calls.
   Else                ' N > 1, so call Factorial again.
      Return Factorial(N - 1) * N
   End If
End Function

[indinfer]

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.

[Evil_Giraffe]

If I am mistaken, I hope someone will post to explain my error.

I didn't read your explanation, but I agree it's not tail recursion, because no matter which side of the * operator you put the recursive call, the * operation comes last.

[Niya]

I can confirm that the VB.Net compiler doesn't optimize for tail-end recursion. Take this function:-

'
    Public Function FacTailRec(ByVal acc As Integer, ByVal n As Integer)
        If n < 2 Then Return acc
        Return FacTailRec(n * acc, n - 1)
    End Function

The VB.Net compiler produces this MSIL for the above function:-

;
.method public instance object  FacTailRec(int32 acc,
                                           int32 n) cil managed
{
  // Code size       24 (0x18)
  .maxstack  4
  .locals init ([0] object FacTailRec)
  IL_0000:  ldarg.2
  IL_0001:  ldc.i4.2
  IL_0002:  bge.s      IL_000b
  IL_0004:  ldarg.1
  IL_0005:  box        [mscorlib]System.Int32
  IL_000a:  ret
  IL_000b:  ldarg.0
  IL_000c:  ldarg.2
  IL_000d:  ldarg.1
  IL_000e:  mul.ovf
  IL_000f:  ldarg.2
  IL_0010:  ldc.i4.1
  IL_0011:  sub.ovf
  IL_0012:  callvirt   instance object WindowsApplication1.Form1::FacTailRec(int32,
                                                                             int32)
  IL_0017:  ret
} // end of method Form1::FacTailRec

My understanding is that the optimization changes tail-end calls into loops in order reduce the overhead of function calls like stack space. Notice the above MSIL method is defined to call itself before returning which means tail-end recursion has not been optimized by the VB.Net compiler.

Now this doesn't mean that the JIT doesn't. Its entirely possible that the JIT will make the optimization. Here is an MSDN article that talks about the tail call optimizations in the CLR.

[indinfer]

I can confirm that the VB.Net compiler doesn't optimize for tail-end recursion. Take this function:-

'
    Public Function FacTailRec(ByVal acc As Integer, ByVal n As Integer)
        If n < 2 Then Return acc
        Return FacTailRec(n * acc, n - 1)
    End Function

By the way, your example is correct. My example was wrong because I put "If n = 1 Then Return 1" I should have put "If n = 1 Then Return CumulativeResult". I should have tested my code even though I "know" what it does. So, I have gone back and corrected my post.

Thank you for posting your example. And I believe that your example is indeed tail recursion.

And I think that you have demonstrated that we cannot rely on VB to optimize tail recursion. I did not learn to read MSIL. But I do see this recursive call:

IL_0012: callvirt instance object WindowsApplication1.Form1::FacTailRec(int32, int32)

But we should not see a recursive call if it is optimized out! VB does not optimize out recursive calls.

[Niya]

I did not learn to read MSIL. But I do see this recursive call:
IL_0012: callvirt instance object WindowsApplication1.Form1::FacTailRec(int32, int32)
But we should not see a recursive call if it is optimized out! VB does not optimize out recursive calls.

Exactly. That would have been optimized to a loop. In such a case you would have seen compare and jump instructions but instead it calls itself passing the arguments on the stack.

I suppose that the MSIL is from the regular VB compiler (whatever it is called) not from the Just-In-Time (JIT) compiler?
Regardless, I would feel shaky relying on the optimization.

The JIT is the component of the CLR that turns that MSIL code into machine code on the fly to be executed by the CPU. According to the link I posted, later versions of the CLR take tail-recursion optimization into account when compiling MSIL.

[Donahue]

No,both C# and VB.NET don't.F# does.

[Niya]

The F# compiler has to, its a functional language where recursion would be as common as loops in imperative languages. But more importantly, the JIT according to the link I posted, didn't consider tail-recursive optimizations too seriously and there are too many conditions that prevent its use so I would guess the F# compiler guys would have to take matters into their own hands and do the optimization at the MSIL level so they wouldn't be at the mercy of the JIT. When dealing with a functional language, tail-recursive optimizations must be taken seriously.