递归函数（二）：编写递归函数的思路和技巧

递归，是一个熟悉而陌生的概念，说它熟悉，是因为人们经常提起它，

而说它陌生，指的是人们在实际编程中几乎不会主动使用它。

给定一个问题，如果本质上它能看做一个调用自身的规模较小的一个子问题来求解，

那么给出一个递归的算法解，就是很自然的。

然而，即使是这样，编制一个递归函数也是一件令人头疼的事情。

本系列文章的目的，可能并不局限于指出如何编写一个递归函数，

而是期望想从递归函数开始，了解它相关的科学知识，以达到对不同领域触类旁通的效果。

1. 从一个简单的例子开始

首先，我们来重温一下递归的概念，

维基百科上是这样描述的，

递归（recursion），在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

我们来看一个简单的例子吧。（Haskell代码

fact :: Int -> Int
fact 1 = 1
fact n = n * fact (n-1)

在这个例子中，

第一行fact :: Int -> Int表示了fact函数的类型，

第二行和第三行定义了函数fact，

我们看到第三行，在对fact函数定义的时候，等式右边又出现了fact，

这样定义的函数fact是递归的。

我们调用一下fact，来看看结果，

fact 10
3628800

嗯嗯，fact就是阶乘函数。

2. 写递归函数的步骤

那么，给定一个问题，我们编写一个递归函数，要如何开始呢？

####（1）递推式

首先，我们要找到“递推式”。

例如，在数学上阶乘的定义是，，这样的表述形式，不具有递推性。

我们先要想办法把用表示出来。

经过思考之后，我们可以证明，，

于是，我们就走出了关键的第一步，得到了“递推式”。

####（2）找出终止条件

有了“递推式”还不行，我们还需要确定递推在什么时候终止。

我们知道，，，等等，

因此，我们只需要指定，那么递推就会在，当的时候终止了。

终止，就是不再调用规模更小的问题了。

这时，终止条件是。

####（3）用数学归纳法证明解的正确性

这一步是很重要的，有很多人都缺少证明递推式正确性的环节，

但是，考虑到介绍数学归纳法及其扩展会占用不少篇幅，

这里先略去，下一篇我们再回来讨论它。

这里，我们先假定，根据“递推式”和“终止条件”，使用数学归纳法，

我们已经证明了这样定义的就是。

####（4）根据递推式和终止条件，编写程序

有了“递推式”和“终止条件”，再编写程序就水到渠成了。

很多人一上来就开始编码，就会感觉毫无头绪。

我们再来看下那段程序，

fact :: Int -> Int
fact 1 = 1
fact n = n * fact (n-1)

这不就是“递推式”和“终止条件”的忠实表示吗？

我们用fact 1 = 1表示了，

用fact n = n * fact (n-1)表示了。

3. 小技巧

我们再看个复杂一点的例子。

在实际项目中，我们可能会遇到循环n次的场景，

在循环过程中，我们会根据索引进行运算，然后将某些符合条件的运算放到最终的结果中。

例如，我们选择10以内的所有偶数，

[x|x <- [0..9], x `mod` 2 == 0]
[0,2,4,6,8]

使用以上列表解析（list comprehension）的方法，我们可以快速得到结果。

但是这里，我们想要拿它来举例，介绍一个编写递归函数常用的小技巧。

为了通用性，我们考虑循环n次，将索引传入函数fn，根据fn的返回值，将结果放入一个列表中。

完成这个功能的函数我们记为myLoop。

####（1）困境

根据前文介绍的编写步骤，我们需要先找到“递推式”和“终止条件”。

“终止条件”怎么写呢？

假如我们定义的递归函数称为myLoop，那么就是终止条件，它应该返回一个列表。

但是这个列表在参数中没有，它随着递归调用的过程“积累”得到的。

好吧，那我们看“递推式”。

要用的结果计算出来，

我们需要先用索引调用fn，然后再根据fn的返回值，放入结果列表，再继续调用。

可是，索引从哪来呢？（n不是索引，因为索引从0开始，而n是逐渐变小的。

这是两个典型的困难，

其一，我们在递归的过程中“积累”了某些东西，

其二，我们需要传递和递归过程相关的“索引”。

####（2）解法

这时候，我们的小技巧就有用武之地了。

我们可以编写一个辅助的递归函数，通过增加参数的办法，提高灵活性。

例如，我们可以编写一个辅助函数myLoop'，然后用myLoop'来实现myLoop。

myLoop :: Int -> (Int -> Maybe a) -> [a]
myLoop n fn = myLoop' n 0 fn []

myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a] -> [a]
myLoop' 0 i fn lst = lst
myLoop' n i fn lst = case fn i of
  Just x -> myLoop' (n-1) (i+1) fn (lst++[x])
  Nothing -> myLoop' (n-1) (i+1) fn lst

以上，我们为myLoop'增加了参数i和lst，分别表示“索引”和“积累”的列表。

然后，myLoop就可以用myLoop'来实现了。

别忘了测试一下最终的结果，

myLoop 10 (\x -> if x `mod` 2 == 0 then Just x else Nothing)
[0,2,4,6,8]

####（3）其他考虑

合理的利用递归函数的返回值，会减少附加参数的数量，例如，

myLoop :: Int -> (Int -> Maybe a) -> [a]
myLoop n fn = myLoop' n 0 fn

myLoop' :: Int -> Int -> (Int -> Maybe a) -> [a]
myLoop' 0 i fn = []
myLoop' n i fn = case fn i of
  Just x -> x:(myLoop' (n-1) (i+1) fn)
  Nothing -> myLoop' (n-1) (i+1) fn

但最终得到的递归函数就不是尾递归了，

关于尾递归，我们将在后续文章中讨论它。

参考

维基百科 - 递归

维基百科 - 递推关系式