Scala 函數(shù)–尾遞歸

函數(shù)–尾遞歸

在前面的文章中我們提到過可以使用遞歸函數(shù)來消除需要使用 var 變量的 while 循環(huán)。下面為一個(gè)使用逼近方法求解的一個(gè)遞歸函數(shù)表達(dá)：

def approximate(guess: Double) : Double =
  if (isGoodEnough(guess)) guess
  else approximate(improve(guess))

通過實(shí)現(xiàn)合適的 isGoodEnough 和 improve 函數(shù)，說明這段代碼在搜索問題中經(jīng)常使用。 如果你打算 approximate 運(yùn)行的快些，你很可能使用下面循環(huán)來實(shí)現(xiàn)什么的算法：

def approximateLoop(initialGuess: Double) : Double = {
  var guess = initialGuess
  while(!isGoodEnough(guess))
    guess=improve(guess)
  guess
 } 

那么這兩種實(shí)現(xiàn)哪一種更可取呢？ 從簡潔度和避免使用 var 變量上看，使用函數(shù)化編程遞歸比較好。但是有 whil e循環(huán)是否運(yùn)行效率更高些？實(shí)際上，如果我們通過測試，兩種方法所需時(shí)間幾乎相同，這聽起來有些不可思議，因?yàn)榛卣{(diào)函數(shù)看起來比使用循環(huán)要耗時(shí)得多。

其實(shí)，對于 approximate 的遞歸實(shí)現(xiàn)，Scala 編譯器會做些優(yōu)化，我們可以看到 approximate 的實(shí)現(xiàn)，最后一行還是調(diào)用 approximate 本身，我們把這種遞歸叫做尾遞歸。Scala 編譯器可以檢測到尾遞歸而使用循環(huán)來代替。因此，你應(yīng)該習(xí)慣使用遞歸函數(shù)來解決問題，如果是尾遞歸，那么在效率時(shí)不會有什么損失。

跟蹤尾遞歸函數(shù)

一個(gè)尾遞歸函數(shù)在每次調(diào)用不會構(gòu)造一個(gè)新的調(diào)用棧(stack frame)。所有遞歸都在同一個(gè)執(zhí)行棧中運(yùn)行，如果你在調(diào)試時(shí)，如果在尾遞歸中調(diào)試錯(cuò)誤，不會看到嵌套的調(diào)用棧，比如下面的代碼，非尾遞歸的一個(gè)實(shí)現(xiàn)：

scala> def boom(x:Int):Int=
     |   if(x==0) throw new Exception("boom!") else boom(x-1) + 1
boom: (x: Int)Int

scala> boom(5)
java.lang.Exception: boom!
  at .boom(<console>:8)
  at .boom(<console>:8)
  at .boom(<console>:8)
  at .boom(<console>:8)
  at .boom(<console>:8)
  at .boom(<console>:8)
  ... 32 elided

boom 不是一個(gè)尾遞歸，因?yàn)樽詈笠恍袨橐粋€(gè)遞歸加一操作，可以看到調(diào)用 boom(5)的調(diào)用棧，為多層。

我們修改這段代碼，使它構(gòu)成一個(gè)尾遞歸：

scala> def bang(x:Int):Int=
     |        if(x==0) throw new Exception("boom!") else bang(x-1)
bang: (x: Int)Int

scala> bang(5)
java.lang.Exception: boom!
  at .bang(<console>:8)
  ... 32 elided

這一次，只看到一層調(diào)用棧，Scala 編譯器將尾遞歸優(yōu)化從循環(huán)實(shí)現(xiàn)，如果你不想使用這個(gè)特性，可以添加 scalac 編譯參數(shù) -g:notailcalls 來取消這個(gè)優(yōu)化，此后，如果拋出異常，尾遞歸也會顯示多層調(diào)用棧。

尾遞歸的一些局限性

目前來說，Scala 編譯器只能對那些直接實(shí)現(xiàn)尾遞歸的函數(shù)，比如前面的 approximate 和 bang，如果一個(gè)函數(shù)間接實(shí)現(xiàn)尾遞歸，比如下面代碼：

def isEven(x:Int): Boolean =
  if(x==0) true else isOdd(x-1)
def isOdd(x:Int): Boolean=
  if(x==0) false else isEven(x-1)

isEven 和 isOdd 事件也是為遞歸，但不是直接定義的尾遞歸，scala 編譯器無法對這種遞歸進(jìn)行優(yōu)化。