从面向过程中的循环控制语句，转变到函数式编程中无处不在的递归，往往需要有一个适应的过程。
本文以求一个列表的全排列为例，描述一种从数学归纳法的角度来理解递归的方式，使用这种思路可以更加容易地写出正确的递归来。
数学归纳法的原理在于：首先证明在某个起点值时命题成立，然后证明从一个值到下一个值的过程有效。同样地，如果我们能求得某一个起点的值f(1)，那么，只要我们知道如何在f(N-1)的基础上求得f(N)，递归的问题就可以解决了。以此为思路，递归语句就不那么难理解了，也不那么难写了。
以求一个列表的全排列为例说明这个过程。比如，对于[1,2,3]这样的序列，要求返回 ［1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1］。
递归的起点是只有一个元素的情况，也就是：
perms([X]) -> ［X］;
对于列表L中的每一个元素X，如果除X之外的子列表[L--X]的全排列已经求出来了，那么整个列表L的全排列就可以求出来了；它们之间的关系是:把X添加在[L--X]的全排列中每一个结果的头部。
例如，如果X是1，除了1之外的子列表[L--X]的全排列为[ [2,3], [3,2] ]，那么把1加到每个结果元素的头部，得到[ [1,2,3], [1,3,2] ]；同理，分别将X对应为2和3，执行相同的过程就可以得到最终的结果[ [1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1] ]。
用Erlang代码表达就是这样：
perms([X]) -> ［X］;
perms(L) -> [ [X|T] || X<-L, T<-perms(L--[X])].
对于这个问题，还可以有另外一种解决的思路。对于一个列表L，如果除第一个元素H之外的子列表的全排列集已经求出来了，再将H插入到此集中每一个元素的每一个位置就可以了。
例如：[1,2,3]的子列表[2,3]的全排列是[ [2,3], [3,2] ]，则将1插入 [2,3]和[3,2]中的每一个位置，分别得到[ [1,2,3],[2,1,3],[2,3,1] ]和[ [1,3,2], [3,1,2],[3,2,1] ]，然后将这两个列表合并即可得到最终的结果。
用代码表示就是：
perms([X]) -> ［X］;
perms([H|T]) -> lists:append([interleave(H, R) || R <- perms(T)]).
其中interleave的实现如下：
interleave(X, []) -> ［X］;
interleave(X, [H|T]) ->
［X|[H|T］ | ［H|R] || R <- interleave(X, T)］.
网友评论