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

為什么遞歸會受到忽視

為 了回答這一問題，必須先說到編程范式。在所有的編程范式中，面向對象編程（Object-Oriented Programming）無疑是***的贏家。看看網上的招聘啟事，無一例外，會要求應聘者熟練掌握面向對象編程。但其實面向對象編程并不是一種嚴格意義上 的編程范式，嚴格意義上的編程范式分為：命令式編程（Imperative Programming）、函數式編程（Functional Programming）和邏輯式編程（Logic Programming）。面向對象編程只是上述幾種范式的一個交叉產物，更多的還是繼承了命令式編程的基因。遺憾的是，在長期的教學過程中，只有命令式 編程得到了強調，那就是程序員要告訴計算機應該怎么做，而不是告訴計算機做什么。而遞歸則通過靈巧的函數定義，告訴計算機做什么。因此在使用命令式編程思 維的程序中，不得不說，這是現在多數程序采用的編程方式，遞歸出鏡的幾率很少，而在函數式編程中，大家可以隨處見到遞歸的方式。下面，我們就通過實例，為 大家展示遞歸如何作為一種普遍方式，來解決編程問題的。

一組簡單的例子

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

清單 1. 數列求和

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

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

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

清單 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 

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

讓我們再看一個例子：如何反轉一個字符串？比如給定一個字符串"abcd"，經過反轉之后變為 "dcba"。同樣的，我們可以做一個大膽的假設，假設后續字符串已經反轉過來，那么接上***個字符，整個字符串就反轉過來了。對于一個只有一個字符的字符串，不需要反轉，這是我們這個遞歸算法的邊界條件。程序實現如下：

清單 3. 反轉字符串

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

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

清單 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 表達式。但這一切都使程序變得更符合算法的核心思想，更加易讀。

尾遞歸

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

清單 5. 遞歸求階乘

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

當遞歸調用 n – 1的階乘時，由于需要保存前面的 n，必須分配一個新的函數棧，這樣當 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) 
} 

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

一道面試題

也許有的讀者看了上面的例子后，還是感到不能信服：雖然使用遞歸會讓程序變得簡潔易懂，但我用循環也一樣可以實現，大不了多幾行代碼而已，而且我還 不用知道什么尾遞歸，寫出的程序就是效率***的。那我們一起來看看下面這個問題：有趣的零錢兌換問題。題目大致如下：假設某國的貨幣有若干面值，現給一張 大面值的貨幣要兌換成零錢，問有多少種兌換方式。這個問題經常被各大公司作為一道面試題，不知難倒了多少同學，下面我給出該問題的遞歸解法，讀者們可以試 試該問題的非遞歸解法，看看從程序的易讀性，及代碼數量上，兩者會有多大差別。該問題的遞歸解法思路很簡單：首先確定邊界條件，如果要兌換的錢數為 0，那么返回 1，即只有一種兌換方法：沒法兌換。這里要注意的是該問題計算所有的兌換方法，無法兌換也算一種方法。如果零錢種類為 0 或錢數小于 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) 
} 

結束語

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

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