以遞歸方式思考
遞歸通過靈巧的函數(shù)定義溃卡，告訴計(jì)算機(jī)做什么。在函數(shù)式編程中，隨處可見遞歸思想的運(yùn)用参滴。
下面給出幾個(gè)遞歸函數(shù)的例子：
object RecursiveExample extends App{
// 數(shù)列求和例子
def sum(xs: List[Int]): Int =
if (xs.isEmpty)
1
else
xs.head + sum(xs.tail)
// 求最大值例子
def max(xs: List[Int]): Int =
if (xs.isEmpty)
throw new NoSuchElementException
else if (xs.size == 1)// 遞歸的邊界條件
xs.head
else
if (xs.head > max(xs.tail)) xs.head else max(xs.tail)
// 翻轉(zhuǎn)字符串
def str_reverse(xs: String): String =
if (xs.length == 1)
xs
else
str_reverse(xs.tail) + xs.head
// 快速排序例子
def quicksort(ls: List[Int]): List[Int] = {
if (ls.isEmpty)
ls
else
quicksort(ls.filter(_ < ls.head)) ::: ls.head :: quicksort(ls.filter(_ > ls.head))
//quicksort(ls.filter(x => x < ls.head)) ::: ls.head :: quicksort(ls.filter(x => x > ls.head))
}
}
我們以上面代碼最后一個(gè)快速排序函數(shù)為例，使用遞歸的方式锻弓，其代碼實(shí)現(xiàn)非常的簡(jiǎn)潔和通俗易懂砾赔。遞歸函數(shù)的核心是設(shè)計(jì)好遞歸表達(dá)式，并且確定算法的邊界條件青灼。上面的快速排序中暴心，認(rèn)為空列表就是排好序的列表，這就是遞歸的邊界條件杂拨，這個(gè)條件是遞歸終止的標(biāo)志专普。
尾遞歸
遞歸算法需要保持調(diào)用堆棧，效率較低弹沽，如果調(diào)用次數(shù)較多檀夹，會(huì)耗盡內(nèi)存或棧溢出。然而策橘，尾遞歸可以克服這一缺點(diǎn)炸渡。
尾遞歸是指遞歸調(diào)用是函數(shù)的最后一個(gè)語句，而且其結(jié)果被直接返回役纹，這是一類特殊的遞歸調(diào)用偶摔。由于遞歸結(jié)果總是直接返回，尾遞歸比較方便轉(zhuǎn)換為循環(huán)促脉，因此編譯器容易對(duì)它進(jìn)行優(yōu)化辰斋。
遞歸求階乘的經(jīng)典例子
普通遞歸求解的代碼如下：
def factorial(n: BigInt): BigInt = {
if (n <= 1)
1
else
n * factorial(n-1)
}
上面的代碼，由于每次遞歸調(diào)用n-1的階乘時(shí)瘸味，都有一次額外的乘法計(jì)算宫仗，這使得堆棧中的數(shù)據(jù)都需要保留。在新的遞歸中要分配新的函數(shù)棧旁仿。
運(yùn)行過程就像這樣：
factorial(4)
--------------
4 * factorial(3)
4 * (3 * factorial(2))
4 * (3 * (2 * factorial(1)))
4 * (3 * (2 * 1))
而下面是一個(gè)尾遞歸版本藕夫，在效率上孽糖，和循環(huán)是等價(jià)的：
import scala.annotation.tailrec
def factorialTailRecursive(n: BigInt): BigInt = {
@tailrec
def _loop(acc: BigInt, n: BigInt): BigInt =
if(n <= 1) acc else _loop(acc*n, n-1)
_loop(1, n)
}
這里的運(yùn)行過程如下：
factorialTailRecursive(4)
--------------------------
_loop(1, 4)
_loop(4, 3)
_loop(12, 2)
_loop(24, 1)
該函數(shù)中的_loop在最后一步，要么返回遞歸邊界條件的值毅贮，要么調(diào)用遞歸函數(shù)本身办悟。
改寫成尾遞歸版本的關(guān)鍵：
尾遞歸版本最重要的就是找到合適的累加器，該累加器可以保留最后一次遞歸調(diào)用留在堆棧中的數(shù)據(jù)滩褥，積累之前調(diào)用的結(jié)果病蛉，這樣堆棧數(shù)據(jù)就可以被丟棄，當(dāng)前的函數(shù)椆寮澹可以被重復(fù)利用铺然。
在這個(gè)例子中，變量acc就是累加器酒甸，每次遞歸調(diào)用都會(huì)更新該變量魄健，直到遞歸邊界條件滿足時(shí)返回該值。
對(duì)于尾遞歸插勤，Scala語言特別增加了一個(gè)注釋@tailrec沽瘦，該注釋可以確保程序員寫出的程序是正確的尾遞歸程序，如果由于疏忽大意农尖，寫出的不是一個(gè)尾遞歸程序其垄，則編譯器會(huì)報(bào)告一個(gè)編譯錯(cuò)誤，提醒程序員修改自己的代碼卤橄。
菲波那切數(shù)列的例子
原始的代碼很簡(jiǎn)單：
def fibonacci(n: Int): Int =
if (n <= 2)
1
else
fibonacci(n-1) + fibonacci(n-2)
尾遞歸版本用了兩個(gè)累加器绿满，一個(gè)保存較小的項(xiàng)acc1，另一個(gè)保存較大項(xiàng)acc2：
def fibonacciTailRecursive(n: Int): Int = {
@tailrec
def _loop(n: Int, acc1: Int, acc2: Int): Int =
if(n <= 2)
acc2
else
_loop(n-1, acc2, acc1+acc2)
_loop(n, 1, 1)
}
幾個(gè)列表操作中使用尾遞歸的例子
求列表的長(zhǎng)度
def lengthTailRecursive[A](ls: List[A]): Int = {
@tailrec
def lengthR(result: Int, curList: List[A]): Int = curList match {
case Nil => result
case _ :: tail => lengthR(result+1, tail)
}
lengthR(0, ls)
}
翻轉(zhuǎn)列表
def reverseTailRecursive[A](ls: List[A]): List[A] = {
@tailrec
def reverseR(result: List[A], curList: List[A]): List[A] = curList match {
case Nil => result
case h :: tail => reverseR(h :: result, tail)
}
reverseR(Nil, ls)
}
去除列表中多個(gè)重復(fù)的元素
這里要求去除列表中多個(gè)連續(xù)的字符窟扑，只保留其中的一個(gè)喇颁。
// If a list contains repeated elements they should be replaced with
// a single copy of the element.
// The order of the elements should not be changed.
// Example:
// >> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
// >> List('a, 'b, 'c, 'a, 'd, 'e)
def compressTailRecursive[A](ls: List[A]): List[A] = {
@tailrec
def compressR(result: List[A], curList: List[A]): List[A] = curList match {
case h :: tail => compressR(h :: result, tail.dropWhile(_ == h))
case Nil => result.reverse
}
compressR(Nil, ls)
}
轉(zhuǎn)載請(qǐng)注明作者Jason Ding及其出處
Github博客主頁(http://jasonding1354.github.io/)
GitCafe博客主頁(http://jasonding1354.gitcafe.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
簡(jiǎn)書主頁(http://www.reibang.com/users/2bd9b48f6ea8/latest_articles)
**Google搜索jasonding1354進(jìn)入我的博客主頁
