即使有多个不同的递归调用，也可以针对尾递归优化函数吗? [英] Can a function be optimized for tail recursion even when there are more than one distinct recursive calls?

问题描述

正如我在最近的SO问题中提到的那样，我正在通过解决 Project Euler 问题来学习F#.

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

我现在对问题3 有一个有效的答案:

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

但是，由于有2条执行路径可以导致对findLargestPrimeFactor的不同调用，因此我不确定可以针对尾部递归对其进行优化.所以我想出了这个:

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

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

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.

所以我的问题:

1. 即使有两个不同的递归调用，第一个实现也可以针对尾递归进行优化吗?
2. 如果两个版本都可以针对尾部递归进行优化，那么有没有一个版本比另一个版本更好(功能更多"，速度更快等)?

推荐答案

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

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

递归分支的数量与尾递归正交.您的第一个函数是尾递归，因为findLargestPrimeFactor是两个分支上的最后一个操作.如有疑问，可以尝试在Release模式(默认情况下启用尾部调用优化选项)下运行该功能，并观察结果.

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.

要挑剔，使用elif关键字，第一个变体较短:

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.

这篇关于即使有多个不同的递归调用，也可以针对尾递归优化函数吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！