《高階Perl》——1.2 階乘

假設有一個有n個不同條目的清單。為了具體點，假設這些條目是字母表的字母。這樣一個清單有多少種不同的排列次序呢？顯然，因為答案依賴于n，是以它是n的函數。這個函數稱為階乘函數（factorial function）。n的階乘就是n個不同條目的不同的排列次序的數量。通常以一個字尾!标記，這樣n的階乘就是n!。一般不同的次序稱為排列（permutation）。

下面計算一些階乘。顯然，隻有一個條目的清單隻有一種排列，是以1!=1。兩個條目的清單有兩種排列：a-b和b-a。少許筆算可以發現3個條目有6種排列：

如何确定沒有遺漏呢？不難想出一種建構所有可能排列的方法，第4章将介紹一個把它們都列出來的程式。這裡有種方法可以做到。可以給一個兩條目的清單添加一個新條目制造任何3條目的清單。從兩條目清單開始時有兩種選擇：ab和ba。每種情況下，在何處放c都有三種選擇：在開始處，在中間，或者在結尾處。一共有2×3=6種選擇，由于每種選擇産生一個不同的3條目的清單，是以就必有六個這樣的清單。上面的左邊一列顯示了把c插入ab得到的所有清單，右邊一列顯示了把c插入ba得到的所有清單，是以上面的展示是完整的。

類似地，如果想知道4個條目有多少排列，就可以用同樣的方法計算。3個條目有6個不同的清單，每個清單有4個位置可插入第4個條目，一共是6×4=24種排列：

現在寫個函數計算，給定任意n，一個n元素清單有多少種排列。

剛才看到了如果知道了n-1個東西的可能的排列的數量，那就能計算n個東西的排列的數量了。要得到一個n項的清單，取(n-1)項清單的(n-1)!個清單中的一個，并把第n項插入清單中n個可能的位置之一。是以，n個條目的排列總數是(n-1)!·n：

這個函數錯了，因為遺漏了終止條件，是以對任何輸入它永不産生結果。要計算factorial(2)，它先嘗試計算factorial(1)。要計算factorial(1)，它先嘗試計算factorial(0)。要計算factorial(0)，它先嘗試計算factorial(-1)。這個過程永遠進行下去。可以修正它，明确地告訴函數0!是什麼，那麼當它遇到0時就不必再遞歸調用了：

現在函數可以正确運作了。

0的階乘是1的原因也許不那麼明顯。回到定義。factorial($n)是給定的$n個元素的清單的排列。factorial(2)是2，因為有兩種方法排列一個兩元素清單：('a', 'b')和('b', 'a')。factorial(1)是1，因為隻有一種方法排列一個單元素清單：('a')。factorial(0)是1，因為隻有一種方法排列一個零元素清單：()。有時人們想要争論0!應該是0，但是()的例子清楚地顯示不是那樣的。

在遞歸函數中得到正确的基本型是極其重要的，因為如果弄錯了，函數将傳回一堆别的結果。如果錯誤地把上面函數中的return 1換成return 0，它将不再是一個計算階乘的函數，相反，它會是一個計算零的函數。

接下來介紹如果遺漏my将會發生什麼。除了沒有對$n的my聲明，下面的函數factorial()和前一個版本一樣：

現在$n是一個全局變量，因為所有的perl變量都是全局的除非用my聲明它們。這就意味着盡管幾個factorial()的副本可以同時運作，但它們都使用同一個全局變量$n。這對函數的行為有什麼影響呢？

考慮一下當調用factorial(1)時會發生什麼。最初，把$n設定為1，第二行的測試失敗，是以函數遞歸調用factorial(0)。factorial(1)的執行體在等待新的函數調用結束。當factorial(0)運作時，把$n設定為0。這次第二行的測試為真，函數立即傳回，産生1。

在等待factorial(0)結果的factorial(1)的執行展現在可以繼續了，來自factorial(0)的結果是1。factorial(1)得到這個1，乘以$n的值，然後傳回結果。但是$n現在是0，因為factorial(0)設它為0，是以結果是1×0=0。這就是factorial(1)最終的錯誤傳回值。它應該是1，而不是0。

類似地，factorial(2)傳回0而不是2，factorial(3)傳回0而不是6，以此類推。

為了運作正确，每個factorial()的執行體需要有它自己私有的$n副本，這樣其他執行體就不會沖突了，這正是my所做的。每次factorial()執行時，都産生一個新的變量專供那次執行用做它的$n。

其他支援遞歸功能的語言都有某些變量與perl的my變量功能類似，每次函數執行時就産生一個新的變量。例如，在c語言裡，在函數内聲明的變量預設有這種表現，除非以别的方式聲明。（在c語言裡，這樣的變量稱為自動（auto）變量，因為它們會自動配置設定和釋放。）使用全局變量或者某種不在每次執行時會配置設定存儲的函數通常無法遞歸地調用該函數，這類函數稱為不可重入的（non-reentrant）。不可重入的函數在還使用fortran（1990年以前不支援遞歸）語言時是非常普遍的，當使用有私有變量的語言（如c）流行時，它就不那麼普遍了。