6

正如我在最近的 SO question中提到的，我正在通过Project Euler问题学习 F#。

我现在对问题 3有一个有效的答案，如下所示：

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

但是，由于有 2 个执行路径可能导致对 的不同调用findLargestPrimeFactor，我不确定它是否可以针对尾递归进行优化。所以我想出了这个：

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

由于只有一条路径导致对 的尾调用findLargestPrimeFactor，我认为它确实会针对尾递归进行优化。

所以我的问题：

  1. 即使有两个不同的递归调用，第一个实现是否可以针对尾递归进行优化？
  2. 如果两个版本都可以针对尾递归进行优化，那么是否有一个比另一个更好（更“功能”、更快等）？
4

2 回答 2

9

您的第一个findLargestPrimeFactor函数是尾递归 - 如果所有递归调用都发生在尾部位置，即使有多个函数，也可以使函数成为尾递归。

这是编译函数的IL：

.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

子句中的第一个分支else（即 if n % p = 0L）从 IL_0013 开始，一直持续到 IL_0024，在那里它无条件地分支回到函数的入口点。

else 子句中的第二个分支从 IL_0026 开始，一直持续到函数结束时，它再次无条件地分支回到函数的开头。F# 编译器已将递归函数转换为包含递归调用的 else 子句的两种情况的循环。

于 2013-02-22T19:16:55.553 回答
6

即使有两个不同的递归调用，第一个实现是否可以针对尾递归进行优化？

递归分支的数量与尾递归正交。您的第一个函数是尾递归的，因为findLargestPrimeFactor它是两个分支上的最后一个操作。如果有疑问，可以尝试在Releasemode 下运行函数（默认开启尾调用优化选项）并观察结果。

如果两个版本都可以针对尾递归进行优化，那么是否有一个比另一个更好（更“功能”、更快等）？

两个版本之间只有细微的差别。第二个版本创建了一个额外的元组，但它不会减慢计算速度。我认为第一个函数更具可读性和直截了当。

为了吹毛求疵，第一个变体使用elif关键字更短：

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

另一个版本是使用模式匹配：

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

由于底层算法相同，因此也不会更快。

于 2013-02-22T19:24:14.997 回答