遞歸算法

簡介

遞歸算法應(yīng)用的場景是要解決的問題和其子問題具有相似性的時候，通過直接或間接的調(diào)用自己求出問題解的方法。它是通過解決一個問題的更小實例來解決一個大的問題的解的算法。遞歸算法有兩個過程，一是調(diào)用過程，二是向上傳遞結(jié)果的過程。3

遞歸程序

在支持自調(diào)用的編程語言中，遞歸可以通過簡單的函數(shù)調(diào)用來完成，如計算階乘的程序在數(shù)學(xué)上可以定義為：

這一程序在Scheme語言中可以寫作：

<pre data-lang="cpp">(define?(factorial?n)??(if?(=?n?0)??????1??????(*?n?(factorial?(-?n?1)))))

不動點組合子

即使一個編程語言不支持自調(diào)用，如果在這語言中函數(shù)是第一類對象（即可以在運行期創(chuàng)建并作為變量處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產(chǎn)生。以下Scheme程序沒有用到自調(diào)用，但是利用了一個叫做Z 算子（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。

<pre data-lang="cpp">(define?Z??(lambda?(f)????((lambda?(recur)?(f?(lambda?arg?(apply?(recur?recur)?arg))))?????(lambda?(recur)?(f?(lambda?arg?(apply?(recur?recur)?arg)))))))(define?fact??(Z?(lambda?(f)???????(lambda?(n)?????????(if?(<=?n?0)?????????????1?????????????(*?n?(f?(-?n?1))))))))

這一程序思路是，既然在這里函數(shù)不能調(diào)用其自身，可以用 Z 組合子應(yīng)用(application)這個函數(shù)后得到的函數(shù)再應(yīng)用需計算的參數(shù)。

尾部遞歸

尾部遞歸是指遞歸函數(shù)在調(diào)用自身后直接傳回其值，而不對其再加運算。尾部遞歸與循環(huán)是等價的，而且在一些語言（如Scheme中）可以被優(yōu)化為循環(huán)指令。 因此，在這些語言中尾部遞歸不會占用調(diào)用堆棧空間。以下Scheme程序同樣計算一個數(shù)字的階乘，但是使用尾部遞歸：1

<pre data-lang="cpp">(define?(factorial?n)??(define?(iter?product?counter)????(if?(>?counter?n)????????product????????(iter?(*?counter?product)??????????????(+?counter?1))))??(iter?1?1))

能夠解決的問題

1. 數(shù)據(jù)的定義是按遞歸定義的。如Fibonacci函數(shù)。
2. 問題解法按遞歸算法實現(xiàn)。如Hanoi問題。
3. 數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。如二叉樹、廣義表等。

遞歸數(shù)據(jù)

數(shù)據(jù)類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數(shù)的定義：“一個自然數(shù)或等于0，或等于另一個自然數(shù)加上1”。Haskell中可以定義鏈表為：

<pre data-lang="cpp">data?ListOfStrings?=?EmptyList?|?Cons?String?ListOfStrings

這一定義相當(dāng)于宣告“一個鏈表或是空串列，或是一個鏈表之前加上一個字符串”?？梢钥闯鏊墟湵矶伎梢酝ㄟ^這一遞歸定義來達到。2