即使有多个不同的递归调用，函数也可以针对尾递归进行优化吗？

Question

正如我在最近的一个SO问题中提到的，我正在通过学习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个执行路径可能导致对findLarggPrimeFactor的不同调用，我不确定它是否可以针对尾递归进行优化。所以我想出了这个：

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. 即使有两个不同的递归调用，第一个实现是否可以针对尾部递归进行优化

Answer 1

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

递归分支的数量与尾部递归正交。第一个函数是尾部递归的，因为findLargestPrimeFactor是两个分支上的最后一个操作。如果有疑问，您可以尝试在释放模式下运行该函数（默认情况下，尾部调用优化选项处于打开状态），并观察结果。

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

两个版本之间只有一点不同。第二个版本创建了一个额外的元组，但它不会降低那么多计算速度。我认为第一个函数更具可读性，更直截了当。

为了挑剔，第一个变体使用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

既然底层算法一样，也不会更快。

Answer 2

第一个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子句中的第一个分支（即，如果p=0L，则从IL_0013开始，一直持续到IL_0024，在此无条件分支回函数的入口点。

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