tail recusion 尾遞歸

時間 2021-01-06 標籤程序語言尾遞歸棧

尾遞歸併不是函數式編程纔有的特性，c++ 裏面也是有的。第一次接觸尾遞歸，是在 UW的coursera課程中，第二次是在sensetime的面試中，面試官問我瞭解尾遞歸嗎，什麼情況下編譯器可以用尾遞歸優化。這裏雖然使用 scala作爲實例講解尾遞歸，但請注意，這並不是scala語言中才有的特性

先說定義，尾遞歸就是一種特殊的遞歸，這種遞歸編譯器可以優化，怎麼優化呢？如果遞歸的過程中可以用被調用函數的棧將調用者函數的棧完全覆蓋掉(而和不覆蓋掉的運行效果是一樣的)，那麼編譯器就可以用尾遞歸優化，

這是課程中的一個定義

example1

def gcd(a:Int,b:Int):Int={
    if(b==0)a
    else gcd(b,a%b)
}

這裏函數 gcd 有一個遞歸調用，可是其實可以完全用遞歸函數的棧覆蓋掉原來的函數，而不產生任何問題

它的函數調用棧大概長成這樣，左非尾遞歸，右尾遞歸

可以見到，右邊用來尾遞歸優化的棧並不會向下繼續增長，而是將原來的棧給覆蓋掉

example 2

def fact(n :Int):Int={
    def factAcc(ret:Int,n :Int):Int={
        if(n==0)ret
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}

這是計算 n! 的尾遞歸版本，可以看到，factAcc的if-else的兩個分支都是直接即時計算的(不需要保存任何中間結果)，也就是說計算，和調用順序是線性的

來看一下普通的版本

def factNotTailRec(n:Int):Int={
    if(n==0)1
    else n*factNotTailRec(n-1)
}

注意 else分支,這裏有兩個計算，除了計算 fact(n-1) 的結果之外，還需要將這個結果乘上n，這使得計算是二叉的，也就是不能直接用 fact(n-1)的結果直接作爲fact(n) 的結果，這帶來了棧的開銷，使得棧中必須要存儲 n。

驗證尾遞歸優化

我們如何驗證編譯器確實做了尾遞歸優化呢？

直接看編譯後的字節碼

這肯定是最直接的方式，但也很難，估計能學到這兒的人並不多

tialrec 聲明

import scala.annotation.tailrec

def gcd(a:Int,b:Int):Int={
    if(b==0)a
    else gcd(b,a%b)
}

def fact(n :Int):Int={
    @tailrec
    def factAcc(ret:Int,n :Int):Int={
        if(n==0)ret
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}

這樣如果 factAcc

不是tail recursion 那麼編譯器會報錯

打印遞歸調用棧

def fact(n :Int):Int={

    def factAcc(ret:Int,n :Int):Int={
        if(n==0){
            val stackArray = Thread.currentThread().getStackTrace()
            stackArray.foreach(println)
            ret
        }
        else factAcc(ret*n,n-1)
    }
    factAcc(1,n)
}


fact(5)

在遞歸結束的時候加了一個打印遞歸調用棧的操作，這裏如果編譯器使用了尾遞歸，我們能看到的是 fact->factAcc 1

不會有中間調用結果

java.lang.Thread.getStackTrace(Thread.java:1559)
$line5.$read$$iw$$iw$.factAcc$1(<console>:16)
$line5.$read$$iw$$iw$.fact(<console>:22)

上面是我本地的輸出結果

可以見到fact 調用之後，直接就是 factAcc$1,沒有其他調用了

reference