1.2.4 遞歸函數

在函數的內部還可以調用函數，不過一般來說再次調用的函數都是其他函數，如果再次調用的函數是函數本身，那么這個函數就是遞歸函數。一個十分經典的例子就是階乘的計算（為了簡化，未考慮0的階乘）。階乘的概念很簡單：n! = nx(n-1)x(n-2)x...2x1。基于此，可以寫出計算階乘的函數，如下所示。

    def factorial_normal(n):
        result = 1
        for i in range(n):
          result = result * n
          n = n -1
        return result

這是一種解決的方法，邏輯比較簡單，下面來看遞歸的實現方式。根據階乘的概念，可以得到n! =nx(n-1)!。基于此，我們可以寫出如下計算階乘的遞歸函數。

    def factorial_recursion(n):
        if n == 1:
          return 1
        return n * factorial_recursion(n -1)

假設執行factorial_recursion(5)，其邏輯如下。

    factorial_recursion(5)
    = 5 * factorial_recursion(4)
    = 5 * 4 * factorial_recursion(3)
    = 5 * 4 * 3 * factorial_recursion(2)
    = 5 * 4 * 3 * 2 * factorial_recursion(1)
    = 5 * 4 * 3 * 2 * 1
    = 120

這兩種方法都是可行的，但是很明顯使用遞歸的方式要更加簡捷一些，而且可以清晰地看出計算的邏輯。在后面爬蟲斷線重連機制的實現上就使用了遞歸函數，它使得爬蟲程序更加穩健。除此之外，遞歸在圖的遍歷、數據結構的構造等方面都有十分廣泛的應用。當然，遞歸也有其缺點，在調用次數過多時會造成棧溢出。例如這里計算factorial_recursion(1000)就會報錯：RecursionError: maximum recursion depth exceeded in comparison。