递归

递归简介

命令式编程语言的两个基本概念是条件语句（if、then、else）和循环语句（for、while）。在纯函数式编程中，我们既没有这些语句，因为不存在“语句”，只有“表达式”。然而，前一章提到的守卫方程可以看作是 Haskell 中对 if 语句的对应。同样地，我们可以使用递归来解决通常在命令式语言中通过循环处理的问题。

一个递归函数是指在其定义方程中至少有一次调用自身的函数。举个例子，让我们重新审视引言中的 compoundInterest 函数：

1compoundInterest :: Int -> Double
2compoundInterest 0 = 1000
3compoundInterest n = 1.05 * compoundInterest (n - 1)
4
5main = print (compoundInterest 3)

第一条方程处理的是基础情况，仅针对输入值 0，直接返回结果 1000。第二条方程是递归情况，它利用输入值为 n - 1 时的计算结果，来求得输入值为 n 时的结果。

递归表达式的求值

在开始编写自己的递归函数之前，我们先深入理解包含递归函数的表达式是如何被求值的。
如何得到 compoundInterest 2 的值？

像往常一样，我们寻找第一个与参数 2 匹配的方程，即第二条方程。如同非递归函数一样，我们将表达式替换为该方程右边的部分：

1compoundInterest 2 
2  = 1.05 * compoundInterest (2 - 1)

右边包含另一个 compoundInterest 的调用。为了继续求值，我们需要简化参数 2 - 1，并再次应用 compoundInterest 的第二条方程。

1compoundInterest 2 
2  = 1.05 * compoundInterest (2 - 1)
3  = 1.05 * compoundInterest 1
4  = 1.05 * 1.05 * compoundInterest (1 - 1)

此时，compoundInterest 的参数计算结果为 0，因此我们可以使用第一条方程终止递归。

1compoundInterest 2 
2  = 1.05 * compoundInterest (2 - 1)
3  = 1.05 * compoundInterest 1
4  = 1.05 * 1.05 * compoundInterest (1 - 1)
5  = 1.05 * 1.05 * compoundInterest 0
6  = 1.05 * 1.05 * 1000
7  = 1.1025 * 1000
8  = 1102.5

最终结果为 1102.5。

求值顺序

我们刚才看到的并不是求值 compoundInterest 2 的唯一方式。

在步骤 1.05 * 1.05 * compoundInterest (1 - 1) 处，我们选择先计算 1 - 1 = 0，然后使用 compoundInterest 的第一条方程。但也可以先计算 1.05 * 1.05。两种求值顺序如下所示：

1compoundInterest 2 
2  = 1.05 * compoundInterest (2 - 1)
3  = 1.05 * compoundInterest 1
4  = 1.05 * 1.05 * compoundInterest (1 - 1)
5  = 1.1025 * compoundInterest (1 - 1)
6  = 1.1025 * compoundInterest 0
7  = 1.1025 * 1000
8  = 1102.5

两种方法最终都得到相同的结果。这是 Haskell 表达式的一个普遍特性：
如果对一个表达式应用两种不同的求值策略，且两者都能得出结果，那么结果必然一致。

这是引用透明性的后果。如果我们的函数有副作用（例如向屏幕输出内容），求值顺序可能会影响程序结果。但只要我们处理的是纯函数，这种情况就不会发生。

由于求值顺序不影响表达式的结果，似乎我们无需关心或了解具体的求值顺序。然而，在某些情况下，求值顺序仍然重要（例如程序是否能正常终止）。

1pow2 :: Int -> Int
2pow2 0 = 1
3pow2 n = 2 * pow2 (n - 1)