F# 14：递归

引言

我们将继续 F# 的探索之旅，这次我们将重点关注递归。我们已经在一些地方看到过递归，例如在讨论列表和模式匹配时。因此，有些内容对您来说应该会有点熟悉。

简单示例

让我们从最基本的示例开始，这与我们之前看到的示例类似。这个示例只是将输入列表中的所有元素相加。

let rec sumFunction theList =
    match theList with
    | []    -> 0
    | head::tail -> head + sumFunction tail

printfn "sumFunction [1..10] = %A" (sumFunction [1..10])

运行后会产生以下输出：

这个简短的代码片段有几个要点需要注意，例如：

• 我们必须使用“rec”关键字才能使函数成为递归函数。如果没有使用“rec”关键字，编译器会发出错误。

• 我们对空列表进行了模式匹配。
• 我们使用“::”（cons）模式匹配，这样我们就可以匹配列表的头部和尾部。

现在让我们将注意力转向另一个示例，这次我们将使用众所周知的阶乘示例。下面是递归实现此功能的标准方法：

let rec factorial n = 
    if n = 0 then 1 else n * factorial (n-1)

这看起来不错，让我们来试试。尝试用输入运行它：

printfn "factorial System.Int32.MaxValue = %A" (factorial 10)

运行后确实一切正常，并给出了以下结果：

printfn "factorial System.Int32.MaxValue = %A" (factorial System.Int32.MaxValue)

那么现在会发生什么？让我们来看看……

现在我们看到了这个输出，这并不太好，实际上，用我以前老板的话来说，这简直是“一团糟”（请原谅我的脏话）。

那么为什么会发生这种情况？我们做错了什么？

好吧，如果我们看看实际的 Visual Studio IDE 并查看“CallStack”（调用堆栈）窗口，我们可以找到一些线索来解释为什么会发生这种情况。

因此，我们有大量的调用堆叠在堆栈上。这实际上是由于代码的结构方式。让我们再次检查代码：

let rec factorial n = 
    if n = 0 then 1 else n * factorial (n-1)

可以看到我们使用了 n，但我们还在等待递归调用“factorial”的结果，以便将它们相乘。所有这些调用都需要放置在某个地方，最终它们会被放在堆栈上，最终我们用完了空间，并抛出了 StackOverFlowException（这是完全正确的）。

您应该问自己的是，是否有更好的方法来编写代码来避免这种情况？

是的，有一种方法，它被称为“尾部递归”，它还使用一种称为“累加器模式”的技术。

尾递归

“累加器模式”到底是什么意思？就其本身而言，它意味着我们将一个额外的值传递给函数，这是一个累加值，您可以在每次迭代调用中使用它。这个简单的更改意味着我们不再需要将东西压入堆栈来保存临时值，显然堆栈仍然与递归本身有关，但我们不必将不必要的值压入堆栈。因此，编译器能够优化代码。

好的，让我们看看新的/更好的代码（为了让我不必等太久就能看到结果，我选择了“5”这个较小的值，但请放心，如果您使用此技术处理更大的数字，就不会抛出 StackOverFlowException）。

let factorialProducingForLoop x =
    // Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

printfn "factorialProducingForLoop 5 = %A" (factorialProducingForLoop 5)

可以看到，我使用了一个非递归函数，该函数被调用，而该函数包含一个嵌套函数，该函数执行递归，并用初始累加器值和原始函数输入值调用。

这是此方法有效且正常工作的证明：

为了完全理解非尾部递归版本和更好的尾部递归版本之间的区别，让我们看看它们的反编译源代码（我使用 DotPeek 来反编译代码，但您可以使用任何您喜欢的工具）。

非尾部递归版本

这是未经优化的非尾部递归版本的反编译 C# 代码，可以看到这会严重依赖堆栈，这在下面显示的 Invoke() 方法中很明显，可以看到 Invoke() 方法被一次又一次地调用。

[Serializable]
  internal class factorial\u004015 : FSharpFunc<int, int>
  {
    internal factorial\u004015()
    {
    }

    public override int Invoke(int n)
    {
      if (n == 0)
        return 1;
      else
        return n * this.Invoke(n - 1);
    }
  }

尾部递归版本

这是优化后的尾部递归版本的反编译 C# 代码，可以看到它已被转换为一个简单的 for **循环，该循环**完全包含在对 Invoke() 方法的单次调用中。这让我们处于一个更好/更愉快的位置。

[Serializable]
  internal class tailRecursiveFactorial\u004021 : OptimizedClosures.FSharpFunc<int, int, int>
  {
    internal tailRecursiveFactorial\u004021()
    {
    }

    public override int Invoke(int x, int acc)
    {
      for (; x > 1; {
        int num;
        x = num;
      }
      )
      {
        num = x - 1;
        acc *= x;
      }
      return acc;
    }
  }

  [Serializable]
  internal class factorialProducingForLoop\u004020 : FSharpFunc<int, int>
  {
    internal factorialProducingForLoop\u004020()
    {
    }

    public override int Invoke(int x)
    {
      return FSharpFunc<int, int>.InvokeFast<int>(
            (FSharpFunc<int, FSharpFunc<int, int>>) 
                    new Program.tailRecursiveFactorial\u004021(), x, 1);
    }

我只想再提一点，如果您采用这个已经很棒（并且完全符合预期）的尾部递归代码

let factorialProducingForLoop x =
    // Keep track of both x and an accumulator value (acc)
    let rec tailRecursiveFactorial x acc =
        if x <= 1 then 
            acc
        else 
            tailRecursiveFactorial (x - 1) (acc * x)
    tailRecursiveFactorial x 1

这给了我们这些结果

但反而决定更喜欢这样写，我们**不**创建内部递归函数，而是选择两个独立的函数，并且我们更改了值和累加器的顺序

let rec tailRecursiveFactorial acc x =
    if x <= 1 then 
        acc
    else 
        tailRecursiveFactorial  (acc * x) (x - 1)

let factorialProducingWhileLoop data = tailRecursiveFactorial 1 data
    
printfn "factorialProducingWhileLoop 5 = %A" (factorialProducingWhileLoop 5)

可以看到我们得到了相同的结果，但让我们检查反编译的代码。

[Serializable]
  internal class tailRecursiveFactorial\u004032 : OptimizedClosures.FSharpFunc<int, int, int>
  {
    internal tailRecursiveFactorial\u004032()
    {
    }

    public override int Invoke(int acc, int x)
    {
      while (x > 1)
      {
        int num = acc * x;
        --x;
        acc = num;
      }
      return acc;
    }
  }

  [Serializable]
  internal class factorialProducingWhileLoop\u004037 : FSharpFunc<int, int>
  {
    public FSharpFunc<int, FSharpFunc<int, int>> tailRecursiveFactorial;

    internal factorialProducingWhileLoop\u004037
              (FSharpFunc<int, FSharpFunc<int, int>> tailRecursiveFactorial)
    {
      this.tailRecursiveFactorial = tailRecursiveFactorial;
    }

    public override int Invoke(int data)
    {
      return FSharpFunc<int, int>.InvokeFast<int>(this.tailRecursiveFactorial, 1, data);
    }
  }

可以看到这次，我们在 Invoke() 方法调用中得到了一个 while 循环。

我不知道这是否会为这篇文章增加任何价值，但我只是想看看如果我改变顺序并且没有嵌套函数，而是使用两个函数而不是一个带有内部函数的函数会发生什么。

我想我只是一个极客（并且为此感到自豪）。

回调

还有一种处理递归的方法，它使用基于回调的技术，但说实话，我发现它不太容易理解，而且对于现在来说有点棘手。如果您有兴趣，我相信快速谷歌一下就能找到您想要的东西。

所以最终，这篇关于一个相当复杂主题的帖子相当简短，但我没有太多想说的了。