函數(shù)遞歸
Factorial稱之為階乘止吁，維基百科是這樣描述的“一個(gè)正整數(shù)的階乘是所有小于及等于該數(shù)的正整數(shù)的積佳窑，并且有0的階乘為1。自然數(shù)n的階乘寫(xiě)作n!告嘲〈砦”
遞歸就是程序自己調(diào)用自己（ recursion），簡(jiǎn)單說(shuō)來(lái)就是不斷地重復(fù)執(zhí)行同樣的代碼來(lái)解決問(wèn)題橄唬。
而階乘函數(shù)是遞歸(Haskell)函數(shù)典型示例赋焕。
一般來(lái)說(shuō)，一個(gè)遞歸函數(shù)的定義有兩個(gè)部分仰楚。首先隆判，至少要有一個(gè)底線，就是一個(gè)簡(jiǎn)單的線僧界，越過(guò)此處侨嘀，遞歸會(huì)停止（換言之，此時(shí)函數(shù)會(huì)直接返回值捂襟，而不會(huì)繼續(xù)“遞歸般地”調(diào)用自身咬腕。底線保證了此函數(shù)必定結(jié)束。其次葬荷，是更一般的遞歸區(qū)涨共，若參數(shù)在此范圍內(nèi)就會(huì)以某種形式調(diào)用自身纽帖。
階乘函數(shù)
數(shù)學(xué)上，尤其是組合數(shù)學(xué)举反，有一個(gè)相當(dāng)常用的函數(shù)叫做階乘(Factorial)懊直。
階乘函數(shù)的參數(shù)是一個(gè)自然數(shù)，它會(huì)返回1與此數(shù)之間所有數(shù)的乘積火鼻。比如室囊，6的階乘是 1 × 2 × 3 × 4 × 5 × 6 = 720 。這相當(dāng)有趣魁索，因?yàn)閷?duì)我們來(lái)說(shuō)融撞，它可以用一種遞歸函數(shù)來(lái)表示。
首先，我們比較相鄰兩個(gè)數(shù)的階乘兰迫。
例子: 相鄰數(shù)的階乘
Factorial of 6 = 6 × 5 × 4 × 3 × 2 × 1
Factorial of 5 = 5 × 4 × 3 × 2 × 1
明顯可以看出6的階乘和5的階乘有關(guān)系。6的階乘就是6 × （5的階乘）。讓我們來(lái)看另一個(gè)例子逼庞。
確實(shí)，我們可以看出任何數(shù)字的階乘就是此數(shù)字乘以比此數(shù)小1的數(shù)的階乘吗货。除了一個(gè)例外：0的階乘字逗，我們不會(huì)把0和-1的階乘相乘。事實(shí)上醒陆，我們只是認(rèn)為0的階乘是1（我們就是這樣定義的瀑构，怎么著了，你不同意刨摩？所以寺晌，0是此處遞歸的底線，當(dāng)我們遇到0的時(shí)候澡刹，我們會(huì)立刻說(shuō)答案是1呻征，不需遞歸。我們可以把階乘函數(shù)的定義簡(jiǎn)述如下罢浇。
0的階乘是1陆赋。
任何數(shù)的階乘都是此數(shù)乘以比此數(shù)小一的數(shù)的階乘。
這個(gè)在Haskell中表示為：
例子: 階乘函數(shù)
factorial 0 = 1
factorial n = n * factorial (n-1)
這就定義了一個(gè)新的叫做factorial的函數(shù)嚷闭。第一行表示0的階乘是1攒岛，第二行表示任意別的數(shù)n的階乘等于n乘以 n-1的階乘。注意那個(gè)把n-1括起來(lái)的括话獭：沒(méi)有這個(gè)括弧代碼就會(huì)被解析稱為(factorial n) - 1灾锯；函數(shù)行為的優(yōu)先級(jí)是很高的，會(huì)最先執(zhí)行嗅榕。
我們可以看出乘法如何貫穿整個(gè)遞歸過(guò)程顺饮。
注意吵聪，我們最終的式子中1出現(xiàn)了兩次，因?yàn)榈拙€是0而不是1领突；不過(guò)這造不成什么錯(cuò)誤暖璧，因?yàn)槌?還會(huì)是原來(lái)的數(shù)。如果我們想讓 factorial在1處停下也辦得到君旦，但0做底線符合常理澎办，而且會(huì)很實(shí)用。
還有一點(diǎn)需要注意的：兩個(gè)聲明（一個(gè)是factorial 0的聲明金砍，一個(gè)是factorial n的聲明）的順序很重要局蚀。Haskell會(huì)先匹配第一個(gè)句子，來(lái)決定函數(shù)的定義恕稠。所以琅绅，如果我們把兩句聲明掉個(gè)，第一個(gè)n語(yǔ)句將會(huì)匹配任何數(shù)（包括0）鹅巍。所以語(yǔ)句 factorial 0
的執(zhí)行過(guò)程是去匹配情況n千扶，于是factorial 0的結(jié)果將會(huì)是0 * factorial (-1)，然后就會(huì)沒(méi)完沒(méi)了骆捧。無(wú)限循環(huán)不是我們想要的澎羞。一般來(lái)說(shuō)：特殊情況應(yīng)該置于前，一般情況置于后敛苇。
