一個函數在它的函數體內調用它自身稱為遞歸調用，這種函數稱為遞歸函數。執行遞歸函數將反復調用其自身，每調用一次就進入新的一層，當最內層的函數執行完畢后，再一層一層地由里到外退出。 > 遞歸函數不是 Python 語言的專利，C/C++、Java、C#、JavaScript、PHP 等其他編程語言也都支持遞歸函數。 下面我們通過一個實例，看看遞歸函數到底是如何運作的。 有這樣一個數學題。己知有一個數列：f(0) = 1，f(1) = 4，f(n + 2) = 2*f(n+ 1) +f(n)，其中 n 是大于 0 的整數，求 f(10) 的值。這道題可以使用遞歸來求得。下面程序將定義一個 fn() 函數，用于計算 f(10) 的值。 ``` def fn(n): if n==0: return 1 elif n==1: return 4 else: #函數中調用它自身，就是函數遞歸 return 2*fn(n-1)+fn(n-2) #輸出fn(10)的結果 print("fn(10)的結果是：",fn(10)) ``` 在上面的 fn() 函數體中再次調用了 fn() 函數，這就是函數遞歸。注意在 fn() 函數體中調用 fn 的形式： return 2 * fn(n - 1) + fn(n - 2) 對于 fn(10)，即等于 2*fn(9)+fn(8)，其中 fn(9) 又等于 2*fn(8)+fn(7)……依此類推，最終會計算到 fn(2) 等于 2*fn(1)+fn(0)，即 fn(2) 是可計算的，這樣遞歸帶來的隱式循環就有結束的時候，然后一路反算回去，最后就可以得到 fn(10) 的值。 仔細看上面遞歸的過程，當一個函數不斷地調用它自身時，必須在某個時刻函數的返回值是確定的，即不再調用它自身：否則，這種遞歸就變成了無窮遞歸，類似于死循環。因此，在定義遞歸函數時有一條最重要的規定： 遞歸一定要向已知方向進行。 例如，如果把上面數學題改為如此。己知有一個數列：f(20)=1，f(21)=4，f(n + 2)=2*f(n+1)+f(n)，其中 n 是大于 0 的整數，求 f(10) 的值。那么 f(10) 的函數體應該改為如下形式： ``` def fn(n): if n==20: return 1 elif n==21: return 4 else: #函數中調用它自身，就是函數遞歸 return fn(n+2)-2*fn(n+1) #輸出fn(10)的結果 print("fn(10)的結果是：",fn(10)) ``` 從上面的 fn() 函數來看，當程序要計算 fn(10) 的值時，fn(10) 等于 fn(12)-2*fn(11)，而 fn(11) 等于 fn(13)-2*fn(12)……依此類推，直到 fn(19) 等于 fn(21)-2*fn(20)，此時就可以得到 fn(19) 的值，然后依次反算到 fn(10) 的值。這就是遞歸的重要規則：對于求 fn(10) 而言，如果 fn(0) 和 fn(1) 是已知的，則應該采用 fn(n)=2*fn(n-1)+fn(n-2) 的形式遞歸，因為小的一端已知；如果 fn(20) 和 fn(21) 是已知的，則應該采用 fn(n)=fn(n+2)-2*fn(n+1) 的形式遞歸，因為大的一端已知。 遞歸是非常有用的，例如程序希望遍歷某個路徑下的所有文件，但這個路徑下的文件夾的深度是未知的，那么就可以使用遞歸來實現這個需求。系統可定義一個函數，該函數接收一個文件路徑作為參數，該函數可遍歷出當前路徑下的所有文件和文件路徑，即在該函數的函數體中再次調用函數自身來處理該路徑下的所有文件路徑。 總之，只要在一個函數的函數體中調用了函數自身，就是函數遞歸。遞歸一定要向已知方向進行。