在初學(xué)計算機編程時，我想大多數(shù)人的經(jīng)歷會和作者一樣，學(xué)校為我們挑選一門語言，大多為 C 或 Java，先是基本的數(shù)據(jù)類型，然后是程序控制語句，條件判斷，循環(huán)等，書上會教我們?nèi)绾味x一個函數(shù)，會說程序就是一條一條的指令，告訴計算機該如何操 作。同時，我們還會看到如何定義一個遞歸函數(shù)，用來計算階乘或斐波那契數(shù)列。工作以后，其他的這些基礎(chǔ)還在日復(fù)一日的使用，但遞歸卻很少再被用到，以致我 們很難再用遞歸的方式去解決問題了，為此，我們還有一個借口：遞歸性能差，使用循環(huán)效率高。事實真是這樣的嗎？我們?yōu)樽约耗撤N能力的喪失編織了一個美麗的 謊言，直到越來越多的編程語言變得流行起來，使我們有機會看到各種語言、各種風格寫出的程序，才發(fā)現(xiàn)自己應(yīng)該重新審視遞歸這一概念了。

為什么遞歸會受到忽視

為 了回答這一問題，必須先說到編程范式。在所有的編程范式中，面向?qū)ο缶幊蹋∣bject-Oriented Programming）無疑是***的贏家。看看網(wǎng)上的招聘啟事，無一例外，會要求應(yīng)聘者熟練掌握面向?qū)ο缶幊獭５鋵嵜嫦驅(qū)ο缶幊滩⒉皇且环N嚴格意義上 的編程范式，嚴格意義上的編程范式分為：命令式編程（Imperative Programming）、函數(shù)式編程（Functional Programming）和邏輯式編程（Logic Programming）。面向?qū)ο缶幊讨皇巧鲜鰩追N范式的一個交叉產(chǎn)物，更多的還是繼承了命令式編程的基因。遺憾的是，在長期的教學(xué)過程中，只有命令式 編程得到了強調(diào)，那就是程序員要告訴計算機應(yīng)該怎么做，而不是告訴計算機做什么。而遞歸則通過靈巧的函數(shù)定義，告訴計算機做什么。因此在使用命令式編程思 維的程序中，不得不說，這是現(xiàn)在多數(shù)程序采用的編程方式，遞歸出鏡的幾率很少，而在函數(shù)式編程中，大家可以隨處見到遞歸的方式。下面，我們就通過實例，為 大家展示遞歸如何作為一種普遍方式，來解決編程問題的。

一組簡單的例子

如何為一組整數(shù)數(shù)列求和？按照通常命令式編程的思 維，我們會采用循環(huán)，依次遍歷列表中的每個元素進行累加，最終給出求和結(jié)果。這樣的程序不難寫，稍 微具備一點編程經(jīng)驗的人在一分鐘之內(nèi)就能寫出來。這次我們換個思維，如何用遞歸的方式求和？為此，我們不妨把問題簡化一點，假設(shè)數(shù)列包含 N 個數(shù)，如果我們已經(jīng)知道了后續(xù) N – 1 個數(shù)的和，那么整個數(shù)列的和即為***個數(shù)加上后續(xù) N – 1 個數(shù)的和，依此類推，我們可以以同樣的方式為 N – 1 個數(shù)繼續(xù)求和，直到數(shù)列為空，顯然，空數(shù)列的和為零。聽起來復(fù)雜，事實上我們可以用一句話來總結(jié)：一個數(shù)列的和即為數(shù)列中的***個數(shù)加上由后續(xù)數(shù)字組成的 數(shù)列的和。現(xiàn)在，讓我們用 Scala 語言把這個想法表達出來。

清單 1. 數(shù)列求和

//xs.head 返回列表里的頭元素，即***個元素 
//xs.tail 返回除頭元素外的剩余元素組成的列表 
def sum(xs: List[Int]): Int = 
 if (xs.isEmpty) 0 else xs.head + sum(xs.tail) 

大家可以看到，我們只使用一行程序，就將上面求和的方法表達出來了，而且這一行程序看上去簡單易懂。盡量少寫代碼，這也是 Scala 語言的設(shè)計哲學(xué)之一，較少的代碼量意味著寫起來更加容易，讀起來更加易懂，同時代碼出錯的概率也會降低。同樣的程序，使用 Scala 語言寫出的代碼量通常會比 Java 少一半甚至更多。

上述這個數(shù)列求和的例子并不是特別的，它代表了遞歸對于列表的一種普遍的處理方式，即對一個列表的操作，可轉(zhuǎn)化為對***個元素，及剩余列表的相同操 作。比如我們可以用同樣的方式求一個數(shù)列中的***值。我們假設(shè)已經(jīng)知道了除***個元素外剩余數(shù)列的***值，那么整個數(shù)列的***值即為***個元素和剩余數(shù)列 ***值中的大者。這里需要注意的是對于一個空數(shù)列求***值是沒有意義的，所以我們需要向外拋出一個異常。當數(shù)列只包含一個元素時，***值就為這個元素本 身，這種情況是我們這個遞歸的邊界條件。一個遞歸算法，必須要有這樣一個邊界條件，否則會一直遞歸下去，形成死循環(huán)。

清單 2. 求***值

def max(xs: List[Int]): Int = { 
   if (xs.isEmpty) 
     throw new java.util.NoSuchElementException 
   if (xs.size == 1) 
     xs.head 
   else 
     if (xs.head > max(xs.tail)) xs.head else max(xs.tail) 
}v 

同樣的方式，我們也可以求一個數(shù)列中的最小值，作為一個練習，讀者可下去自行實現(xiàn)。

讓我們再看一個例子：如何反轉(zhuǎn)一個字符串？比如給定一個字符串"abcd"，經(jīng)過反轉(zhuǎn)之后變?yōu)?nbsp;"dcba"。同樣的，我們可以做一個大膽的假設(shè)，假設(shè)后續(xù)字符串已經(jīng)反轉(zhuǎn)過來，那么接上***個字符，整個字符串就反轉(zhuǎn)過來了。對于一個只有一個字符的字符串，不需要反轉(zhuǎn)，這是我們這個遞歸算法的邊界條件。程序?qū)崿F(xiàn)如下：

清單 3. 反轉(zhuǎn)字符串

def reverse(xs: String): String = 
if (xs.length == 1) xs else reverse(xs.tail) + xs.head 

***一個例子是經(jīng)典的快速排序，讀者可能會覺得這個例子算不上簡單，但是我們會看到，使用遞歸的方式，再加上 Scala 簡潔的語言特性，我們只需要短短幾行程序，就可以實現(xiàn)快速排序算法。 快速排序算法的核心思想是：在一個無序列表中選擇一個值，根據(jù)該值將列表分為兩部分，比該值小的那一部分排在前面，比該值大的部分排在后面。對于這兩部分 各自使用同樣的方式進行排序，直到他們?yōu)榭眨@然，我們認為一個空的列表即為一個排好序的列表，這就是這個算法中的邊界條件。為了方便起見，我們選擇*** 個元素作為將列表分為兩部分的值。程序?qū)崿F(xiàn)如下：

清單 4. 快速排序

def quickSort(xs: List[Int]): List[Int] = { 
   if (xs.isEmpty) xs 
   else 
     quickSort(xs.filter(x=>x<xs.head)):::xs.head::quickSort(xs.filter(x=>x>xs.head)) 
} 

當然，為了使程序更加簡潔，作者在這里使用了列表中的一些方法：給列表增加一個元素，連接兩個列表以及過濾一個列表，并在其中使用了 lambda 表達式。但這一切都使程序變得更符合算法的核心思想，更加易讀。

尾遞歸

從上面的例子中我們可以看到，使用遞歸方式寫出的程序通常通俗易懂，這其實代表這兩種編程范式的不同，命令式編程范式傾向于使用循環(huán)，告訴計算機怎 么做，而函數(shù)式編程范式則使用遞歸，告訴計算機做什么。習慣于命令式編程范式的程序員還有一個擔憂：相比循環(huán)，遞歸不是存在效率問題嗎？每一次遞歸調(diào)用， 都會分配一個新的函數(shù)棧，如果遞歸嵌套很深，容易出現(xiàn)棧溢出的問題。比如下面計算階乘的遞歸程序：

清單 5. 遞歸求階乘

def factorial(n: Int): Int = 
if (n == 0) 1 else n * factorial(n - 1) 

當遞歸調(diào)用 n – 1的階乘時，由于需要保存前面的 n，必須分配一個新的函數(shù)棧，這樣當 n很大時，函數(shù)棧將很快被耗盡。然而尾遞歸能幫我們解決這個問題，所謂尾遞歸是指在函數(shù)調(diào)用的***一步，只調(diào)用該遞歸函數(shù)本身，此時，由于無需記住其他變量，當前的函數(shù)棧可以被重復(fù)使用。上面的程序只需稍微改造一下，既可以變成尾遞歸式的程序，在效率上，和循環(huán)是等價的。

清單 6. 尾遞歸求階乘

def factorial(n: Int): Int = { 
   @tailrec 
   def loop(acc: Int, n: Int): Int = 
     if (n == 0) acc else loop(n * acc, n - 1) 
  
   loop(1, n) 
} 

在上面的程序中，我們在階乘函數(shù)內(nèi)部定義了一個新的遞歸函數(shù)，該函數(shù)***一步要么返回結(jié)果，要么調(diào)用該遞歸函數(shù)本身，所以這是一個尾遞歸函數(shù)。該函數(shù)多出一個變量 acc，每次遞歸調(diào)用都會更新該變量，直到遞歸邊界條件滿足時返回該值，即為***的計算結(jié)果。這是一種通用的將非尾遞歸函數(shù)轉(zhuǎn)化為尾遞歸函數(shù)的方法，大家可多加練習，掌握這一方法。對于尾遞歸，Scala 語言特別增加了一個注釋 @tailrec，該注釋可以確保程序員寫出的程序是正確的尾遞歸程序，如果由于疏忽大意，寫出的不是一個尾遞歸程序，則編譯器會報告一個編譯錯誤，提醒程序員修改自己的代碼。

一道面試題

也許有的讀者看了上面的例子后，還是感到不能信服：雖然使用遞歸會讓程序變得簡潔易懂，但我用循環(huán)也一樣可以實現(xiàn)，大不了多幾行代碼而已，而且我還 不用知道什么尾遞歸，寫出的程序就是效率***的。那我們一起來看看下面這個問題：有趣的零錢兌換問題。題目大致如下：假設(shè)某國的貨幣有若干面值，現(xiàn)給一張 大面值的貨幣要兌換成零錢，問有多少種兌換方式。這個問題經(jīng)常被各大公司作為一道面試題，不知難倒了多少同學(xué)，下面我給出該問題的遞歸解法，讀者們可以試 試該問題的非遞歸解法，看看從程序的易讀性，及代碼數(shù)量上，兩者會有多大差別。該問題的遞歸解法思路很簡單：首先確定邊界條件，如果要兌換的錢數(shù)為 0，那么返回 1，即只有一種兌換方法：沒法兌換。這里要注意的是該問題計算所有的兌換方法，無法兌換也算一種方法。如果零錢種類為 0 或錢數(shù)小于 0，沒有任何方式進行兌換，返回 0。我們可以把找零的方法分為兩類：使用不包含***枚硬幣（零錢）所有的零錢進行找零，使用包含***枚硬幣（零錢）的所有零錢進行找零，兩者之和即為所有 的找零方式。***種找零方式總共有 countChange(money, coins.tail)種，第二種找零方式等價為對于 money – conins.head進行同樣的兌換，則這種兌換方式有 countChange(money - coins.head, coins)種，兩者之和即為所有的零錢兌換方式。

清單 7. 零錢兌換問題的遞歸解法

def countChange(money: Int, coins: List[Int]): Int = { 
  if (money == 0) 
    1 
  else if (coins.size == 0 || money < 0) 
    0 
  else 
    countChange(money, coins.tail) + countChange(money - coins.head, coins) 
} 

結(jié)束語

本文通過實例，和大家一起重新審視了遞歸在編程中的應(yīng)用，使用遞歸的方式去編程代表了一種編程思想上的轉(zhuǎn)變，程序員應(yīng)該站在更高的抽象層次上，告訴 計算機做什么，而不是怎么做。遞歸作為一種處理問題的普遍方式，應(yīng)該得到更廣泛的應(yīng)用。事實上，在 Haskell 語言中，不存在 while、for 等命令式編程語言中必不可少的循環(huán)控制語句，Haskell 強迫程序員使用遞歸等函數(shù)式編程的思維去解決問題。作者也鼓勵大家以后碰到問題時，先考慮有沒有好的遞歸的方式實現(xiàn)，看看是否會為我們關(guān)于編程的理解帶來 新的思考。

原文鏈接：http://www.ibm.com/developerworks/cn/java/j-lo-funinscala1/