算法：遞歸

遞歸指一個計算機程式調用其自身。遞歸有兩個基本要素：

（1） 邊界條件：确定遞歸到何時終止，也稱為遞歸出口。

（2） 遞歸模式：大問題是如何分解為小問題的，也稱為遞歸體。

遞歸函數隻有具備了這兩個要素，才能在有限次計算後得出結果。

比如下面的程式，是用于計算高斯求和公式:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-

import sys

def Gauss(n):
    if n==1:
        return 1
    return Gauss(n-1) + n

print Gauss(int(sys.argv[1]))
           

$ python Gauss.py 300
45150
           

在程式中規定了f(1)的值，以及f(n)和f(n-1)的關系。這是數學歸納法思想的展現。想要得到f(n)，必須計算f(n-1)；想要f(n-1)，必須計算f(n-2)……直到f(1)。由于我們已經知道了f(1)的值，我們就可以填補前面所有的空缺，最終傳回f(n)的值。

遞歸是數學歸納法在計算機中的程式實作。使用遞歸設計程式的時候，我們設定base case，并假設我們會獲得n-1的結果，并實作n的結果。這就好像數學歸納法，我們隻關注初始和銜接，而不需要關注具體的每一步。