迭代、遞歸與Tail Call Optimization

jopen 8年前發布 | 7K 次閱讀函數式編程

在程序設計的世界里面有兩種很基本的設計模式，那就是迭代（iterative）和遞歸（recursive）。這兩種模式之間存在著很強的一致性和對稱性。

現在讓我來設計一段程序，計算 n! ， 不能使用任何循環結構 。我們把這個過程封裝成一個函數 calc ，假設 n=4 ，整個計算的 過程（Process） 是這樣的。

calc(4)=4*calc(3)
calc(3)=3*calc(2)
calc(2)=2*calc(1)
calc(1)=1*calc(0)
calc(0)=1

對應的 程序（Procedure） 可以被寫成：

def calc(n):
    """
    Calculate n!

    :param n: N
    """
    if n == 0:
        return 1
    if n < 0:
        raise ValueError
    return n * calc(n - 1)

我在上面特別強調了過程和程序的差別，這對后文很重要。Procedure一般也被翻譯成過程，為了避免沖突，我將它翻譯成程序。過程實際上是一個數學的模型，用文字表述，是比較抽象的；而程序相對而言就是具象化的。程序可以用來實現過程。

將上面的過程展開后可以變成下面這樣，我們將之稱作 過程A 。

calc(4)=4*calc(3)
=4*(3*calc(2))
=4*(3*(2*calc(1)))
=4*(3*(2*(1*calc(0))))
=4*(3*(2*(1*1)))
=4*(3*(2*1))
=4*(3*2)
=4*6
24

計算 n! 的過程不止一種。我們還可以想到另外一種計算過程來計算 4! 。設 result 為最后的結果。

result=1
n=4

result=result*n=4
n=n-1=3
result=result*n=12
n=n-1=2
result=result*n=24
n=n-1=1
result=result*n=24
n=n-1=0

相應的程序實現可以為

def calc(n):
    """
    Calculate n!
    """
    if n < 0:
        raise ValueError
    return calc_iter(n, 1)

def calc_iter(n, result):
    if n == 0:
        return result
    return calc_iter(n - 1, result * n)

整個過程展開就變成了

calc(4)=calc_iter(4, 1)
calc_iter(4, 1)
calc_iter(3, 4)
calc_iter(2, 12)
calc_iter(1, 24)
calc_iter(0, 24)

這個展開后的過程我們稱之為 過程B 。

遞歸與迭代

對比過程A和B，過程A看起來比較“浪費空間”，至少我得打更多的字表達它。它們之間最大的區別是，在過程A中，前一次計算的結果要靠后一次計算的結果以及它本身的參數結合才能得出來。例如在計算 calc(4)=4*calc(3) 的時候， calc(3) 就是下一次計算的結果，而 4 是 calc(4) 本身的參數。

反之，在過程B中，前一次計算的結果和后一次計算的結果都通過參數傳遞。每次計算的參數就是這次計算所需的所有狀態。如果你讀過我寫的 “函數是一等公民”背后的含義，你就會發現這是函數式編程里面純函數的特性。

過程A，這類前一次計算依賴于自身狀態和后一次計算的結果的過程我們就稱之為遞歸過程（Recursive Process），因為它最后總要回到之前的計算中才能獲得最后結果；而過程B，這類每次計算結果僅依賴于自身狀態的過程我們就稱之為迭代過程（Iterative Process）。

Tail Call Optimization (TCO)

如果我們觀察上面的第二段程序，我們會說這是一個遞歸函數，因為它用了函數的遞歸調用。但是我們已經提到了，它實際上是一個迭代過程，而不是遞歸過程。因為每一次調用 calc_iter 的時候，本次計算的結果都能由自身狀態得出來。它完全可以被重寫為

def calc(n):
    """
    Calculate n!
    """
    if n < 0:
        raise ValueError
    result = 1
    while n > 0:
        result, n = result * n, n - 1
    return result

因此，盡管有些函數被寫成了遞歸的形式，它依然可能是表示一個迭代的過程。很有趣的是，盡管它是迭代過程，但是它還是占用了棧空間。如果 n 足夠大的話，這個迭代過程依然可能跟傳統的遞歸函數實現一樣產生棧溢出。

既然每次計算都包含著本次計算所需的所有狀態，那就說明我們實際上沒有必要把前面一次計算的函數調用推入棧中。因為無論如何，我們都不會再用到之前的調用了。這種不將前一次函數調用推入棧中的優化就被稱作Tail Call Optimization。之所以叫Tail Call是因為在用遞歸函數實現迭代過程的時候，對下一次計算過程的調用都在尾部。理由很簡單，因為我們不再需要回到這個函數，所以在遞歸調用之后就不需要有其他的邏輯了。