F#的尾递归编译优化需要再好好优化优化

先来看一道简单的算法题：

给定一个整数序列，给定一个目标值，求出该序列中任意三个数之和中最接近目标值的那个数。

这道题很容易想到的算法：

1. 对序列做从小到大排序
2. 固定其中一个数的下标a，对剩下的两个数双指针b、c，指向a右侧区域（窗口）的两端。根据a、b、c三处值之和与目标值大小关系，窗口不断向内收缩两端的b、c指针，直到找到三者之和等于目标值，或者窗口两端指针重合，此时得到a的当前取值下的较优解。
3. 从左到右遍历a，找到所有a取值的较优解，并选出最优解。

考虑上述算法用F#实现，首先比较容易思考的是使用变量。（毕竟我们跟变量打了许多年交道了）：

let threeSumClosest nums target =
    let sorted = Array.sort nums
    let mutable diff = System.Int32.MaxValue
    let mutable rsl = target
    for a in 0 .. sorted.Length - 2 do
        let mutable b = a + 1
        let mutable c = sorted.Length - 1
        while (diff <> 0 && b < c) do
            let sum = sorted[a] + sorted[b] + sorted[c]
            let rest = abs (sum - target)
            if rest < diff then 
                diff <- rest
                rsl <- sum
            if sum < target then b <- b + 1 
            elif sum > target then c <- c - 1
    rsl

很容易理解对吧。

然而，这代码显然不够“函数”。真正的函数式编程应该不存在变量。咱们尝试下使用纯函数来实现。

用了变量，for、while循环可以随便用。但是如果使用纯函数，while循环基本就再见了（while返回的是unit），for基本只能用来返回序列了。而循环大部分时间会使用递归描述。

此处递归函数定义：对于每层递归，根据当前确定选定的a、b、c，返回a固定、b和c取值在当前b、c值之间时，与目标最小差距的和。

于是，可以写出如下实现：

let threeSumClosest2 nums target =
    let inline min target sum x = if abs (sum - target) < abs (x - target) then sum else x
    let rec inner (nums: int[]) target a b c =
        let sum = nums[a] + nums[b] + nums[c]
        if b >= c then System.Int32.MaxValue
        elif sum = target then sum
        elif sum < target then min target sum <| inner nums target a (b + 1) c
        else min target sum <| inner nums target a b (c - 1)
    let sorted = Array.sort nums
    seq { for i in 0 .. sorted.Length - 2 -> inner sorted target i (i + 1) (sorted.Length - 1) } 
    |> Seq.minBy (fun x -> abs (x - target))

这里已经没有变量了。

然而，这里使用了递归，在数据量上来之后，反复递归会导致性能的下降。

我们考虑将代码优化一下，变成尾递归。F#的编译器会将尾递归自动编译为循环。

尾递归的要诀是：不保存任何中间值。也就是说，递归会一直进行到最后一层，并由最后一层递归的返回作为所有递归层的返回结果。

于是，我们将每次计算的三者之和与之前计算的较优的和进行比较，把更接近目标的值作为中间的较优结果，传递给下一层递归。

优化后代码如下：

let threeSumClosest3 nums target =
    let inline min target sum x = if abs (sum - target) < abs (x - target) then sum else x
    let rec inner (nums: int[]) target almost a b c =
        if a > nums.Length - 2 then almost
        elif b >= c then inner nums target almost (a + 1) (a + 2) (nums.Length - 1)
        else
            let sum = nums[a] + nums[b] + nums[c]
            if sum = target then sum
            else
                let better = min target sum almost
                if sum < target then inner nums target better a (b + 1) c
                else inner nums target better a b (c - 1)
    let sorted = Array.sort nums
    inner sorted target (System.Int32.MaxValue) 0 1 (sorted.Length - 1)

这里的每层递归不在保存任何中间值了。较优值会一路传递到最后一次递归，最后一路返回。

OK，终于要进入本文的重点了。

我们需要验证下代码是不是被编译成了循环，而不是递归调用。

我们查看下编译后的IL代码，将他反编译成C#代码，于是看到了惊掉下巴的奇葩代码：

internal static int inner_00404(int[] nums, int target, int almost, int a, int b, int c)
{
    int num5;
    while (true)
    {
        if (a > nums.Length - 2)
        {
            return almost;
        }

        if (b >= c)
        {
            int[] array = nums;
            int num = target;
            int num2 = almost;
            int num3 = a + 1;
            int num4 = a + 2;
            c = nums.Length - 1;
            b = num4;
            a = num3;
            almost = num2;
            target = num;
            nums = array;
            continue;
        }

        num5 = nums[a] + nums[b] + nums[c];
        if (num5 == target)
        {
            break;
        }

        int num6 = (Math.Abs(num5 - target) >= Math.Abs(almost - target)) ? almost : num5;
        if (num5 < target)
        {
            int[] array2 = nums;
            int num7 = target;
            int num8 = a;
            int num9 = b + 1;
            c = c;
            b = num9;
            a = num8;
            almost = num6;
            target = num7;
            nums = array2;
        }
        else
        {
            int[] array3 = nums;
            int num10 = target;
            int num11 = a;
            int num12 = b;
            c--;
            b = num12;
            a = num11;
            almost = num6;
            target = num10;
            nums = array3;
        }
    }

    return num5;
}

里面先int numXX = target;，紧接着target=numXX;的代码比比皆是。更可气的是有c=c这样的代码。

不过仔细想一想，又没有什么毛病。作为编译器的自动优化，一定要找到通用的规则才行，这个通用规则可以不够搞笑，关键是要稳。上述翻译要解决的问题是：传递给一下次循环的参数，有可能相互之间有运算关系。 如果不把所有的值先算出来，而是算一个赋值一个，可能计算后续参数值的时候，前面的参数已经变化了，导致计算错误。

从上述翻译我们可以猜测编译器的优化逻辑：

1. 建立方法，方法传入的参数作为循环体共享的循环变量。建立循环，循环中的出口对应尾递归中的出口。
2. 按照顺序解析代码，将尾递归的每一个分支放在if中：
   1. 如果该分支没有递归调用，则认为是出口。
      • 通过return返回结果。
      • 由于循环外必须有一个return，所以其中一个会被翻译成break，在循环外return。
      • 又因为这些分支都已经return或者break了，其他分支可以放在主方法体里，而不用放在else里。
   2. 如果该分支有递归调用，则认为需要进入下一层循环。
      • 在主方法体内书写分支逻辑
      • 执行到递归调用时，判断每个参数是否影响到其他参数的变化
        • 不影响其他参数的参数，不需要中间变量，直接进行赋值操作。例如上例中的c。
        • 影响其他参数的参数，先将需要传递给下一次循环的计算结果保存在临时变量中，全部计算完成后再传递给循环共享的变量。

以上是猜测，但是应该八九不离十。可见，尾递归的编译器优化其实并没有那么的智能。感觉还有优化的空间。比如上例中，c=c是完全可以优化掉的。F#还有很长的路要走。