Friday, November 20, 2015

什麼是尾端遞迴 (Tail recusion)


  • 普通recursion:典型的遞迴就是一個函式直接或是間接的調用自己,接著利用函式回傳的值計算出結果。假如使用這個方法,在還沒得到每一個遞迴函式回傳值之前,沒有辦法計算出最後的結果。
  • Tail recursion:不同於普通的recursion,tail recursion是指一個函式在其尾端調用自己,而其結果被直接傳回,也就不需要等待每個函式回傳值。

為了幫助大家能更快的了解兩者的差異,我們將用Scala實作簡單的函式來描述程式執行的過程。假設該函式的功能是計算前N個整數的總合,比如說 recSum(4) = 1 + 2 + 3 + 4 = 10。

  • 普通recursion:
def recSum(x:Int):Int = if(x == 1) x else x + recSum(x - 1)
假如我們把x = 5帶入這個函式,程式將會以下面的方式執行:
recSum(4)
4 + recSum(3)
4 + (3 + recSum(2))
4 + (3 + (2 + recSum(1)))
4 + (3 + (2 + 1))
10
由此可知,函式必須不斷遞迴佔用堆疊,直到最後實際計算總合後才釋放出來。假如遞迴的次數過多,將會導致記憶體的不足。

  • Tail recursion:
def tailRecSum(x:Int, total:Int=0):Int = {
    if(x == 0) total 
    else tailRecSum(x - 1, total + x)
    }
同樣的,我們把x=5帶入函式中,程式則會以下面的方式執行:
tailRecSum(4,0)
tailRecSum(3,4)
tailRecSum(2,7)
tailRecSum(1,9)
tailRecSum(0,10)
10
可以看到在tail recursion每次的遞迴裡,函式結果都是直接回傳的。其中的關鍵就是累加器,也就是程式碼裡的total。表示我們不需要保留之前每一次計算的結果,只需要保留最後一次就可以了。

No comments:

Post a Comment