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:
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.
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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With