Can a function be optimized for tail recursion even when there are more than one distinct recursive calls?

Question

As I mentioned in a recent SO question, I'm learning F# by going through the Project Euler problems.

I now have a functioning answer to Problem 3 that looks like this:

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    else
        if n % p = 0L then findLargestPrimeFactor p (n/p)
        else findLargestPrimeFactor (p + 2L) n

let result = findLargestPrimeFactor 3L 600851475143L

However, since there are 2 execution paths that can lead to a different call to findLargestPrimeFactor, I'm not sure it can be optimized for tail recursion. So I came up with this instead:

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    else
        let (p', n') = if n % p = 0L then (p, (n/p)) else (p + 2L, n)
        findLargestPrimeFactor p' n'

let result = findLargestPrimeFactor 3L 600851475143L

Since there's only one path that leads to a tail call to findLargestPrimeFactor, I figure it is indeed going to be optimized for tail recursion.

So my questions:

1. Can the first implementation be optimized for tail recursion even if there are two distinct recursive calls?
2. If both versions can be optimized for tail recursion, is there one better (more "functional", faster, etc) than the other?

Answer 1

Your first findLargestPrimeFactor function is tail recursive - a function can be made tail recursive if all recursive calls occur in the tail position, even if there are more than one.

Here's the IL of the compiled function:

.method public static int64  findLargestPrimeFactor(int64 p,
                                                    int64 n) cil managed
{
  .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = ( 01 00 02 00 00 00 01 00 00 00 01 00 00 00 00 00 ) 
  // Code size       56 (0x38)
  .maxstack  8
  IL_0000:  nop
  IL_0001:  ldarg.1
  IL_0002:  ldc.i8     0x1
  IL_000b:  bne.un.s   IL_000f
  IL_000d:  br.s       IL_0011
  IL_000f:  br.s       IL_0013
  IL_0011:  ldarg.0
  IL_0012:  ret
  IL_0013:  ldarg.1
  IL_0014:  ldarg.0
  IL_0015:  rem
  IL_0016:  brtrue.s   IL_001a
  IL_0018:  br.s       IL_001c
  IL_001a:  br.s       IL_0026
  IL_001c:  ldarg.0
  IL_001d:  ldarg.1
  IL_001e:  ldarg.0
  IL_001f:  div
  IL_0020:  starg.s    n
  IL_0022:  starg.s    p
  IL_0024:  br.s       IL_0000
  IL_0026:  ldarg.0
  IL_0027:  ldc.i8     0x2
  IL_0030:  add
  IL_0031:  ldarg.1
  IL_0032:  starg.s    n
  IL_0034:  starg.s    p
  IL_0036:  br.s       IL_0000
} // end of method LinkedList::findLargestPrimeFactor

The first branch in the else clause (i.e. if n % p = 0L) starts at IL_0013 and continues until IL_0024 where it unconditionally branches back to the entry point of the function.

The second branch in the else clause starts at IL_0026 and continues until the end of the function where it again unconditionally branches back to the start of the function. The F# compiler has converted your recursive function into a loop for both cases of the else clause which contains the recursive calls.

Answer 2

Can the first implementation be optimized for tail recursion even if there are two distinct recursive calls?

The number of recursive branches is orthogonal with tail recursion. Your first function is tail-recursive since findLargestPrimeFactor is the last operation on both two branches. If in doubt, you can try to run the function in Release mode (where tail call optimization option is turned on by default) and observe results.

If both versions can be optimized for tail recursion, is there one better (more "functional", faster, etc) than the other?

There is just a slight difference between two versions. The second version creates an extra tuple, but it will not slow down computation that much. I consider the first function more readable and straight to the point.

To be nitpicking, the first variant is shorter using elif keyword:

let rec findLargestPrimeFactor p n = 
    if n = 1L then p
    elif n % p = 0L then findLargestPrimeFactor p (n/p)
    else findLargestPrimeFactor (p + 2L) n

Another version is to use pattern matching:

let rec findLargestPrimeFactor p = function
    | 1L -> p
    | n when n % p = 0L -> findLargestPrimeFactor p (n/p)
    | n -> findLargestPrimeFactor (p + 2L) n

Since the underlying algorithm is the same, it will not be faster either.