從面向過程中的循環(huán)控制語句，轉變到函數(shù)式編程中無處不在的遞歸，往往需要有一個適應的過程。

本文以求一個列表的全排列為例，描述一種從數(shù)學歸納法的角度來理解遞歸的方式，使用這種思路可以更加容易地寫出正確的遞歸來。

數(shù)學歸納法的原理在于：首先證明在某個起點值時命題成立，然后證明從一個值到下一個值的過程有效。同樣地，如果我們能求得某一個起點的值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，執(zhí)行相同的過程就可以得到最終的結果[ [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的實現(xiàn)如下：

interleave(X, []) -> ［X］;
interleave(X, [H|T]) ->
        ［X|[H|T］ | ［H|R] || R <- interleave(X, T)］.