1.7　從前有座山，山里有座廟：遞歸之法

遞歸調用是函數內部調用自身的過程。遞歸必須要有結束條件，否則會進入無限遞歸狀態，永遠無法結束。

1. 遞歸函數

訓練1-32：輸入n個整數，倒序輸出所有整數。

2. 遞歸原理

遞歸包括遞推和回歸。遞推指將原問題不斷分解成子問題，直到達到結束條件，返回最近子問題的解；然后逆向逐一回歸，最終到達遞推開始時的原問題，返回原問題的解。

階乘是典型的遞歸調用問題，5的階乘遞推、回歸過程如下圖所示。

訓練1-33：輸入一個整數n，輸出n的階乘。

注意：在遞歸算法中，每一次遞推都需要一個棧空間來保存調用記錄，因此在計算空間復雜度時需要計算遞歸棧的輔助空間。

上圖中的遞推、回歸過程是我們從邏輯思維上推理并用圖形象表達出來的，但其在計算機內部是怎樣處理的呢？計算機使用了一種被稱為“棧”的數據結構，它類似于一個放了一摞盤子的容器，每次放進去一個，拿出來的時候就只能從頂端拿一個，不允許從中間插入或抽取，因此被稱為“后進先出”（Last In First Out，LIFO）。

5的階乘遞推（進棧）過程的形象表達如下圖所示，在實際遞歸中傳遞的是參數的地址。

5的階乘回歸（出棧）過程的形象表達如下圖所示。

從圖中可以很清晰地看到，它首先一步步地把子問題壓入棧，直到得到返回值，再一步步地出棧，最終得到遞歸結果。在運算過程中使用了n個棧空間作為輔助空間。

訓練1-34：輸入一個整數n，輸出斐波那契數列的第n項。

斐波那契數列：1,1,2,3,5,8,13,21,34……

遞歸式表達式如下：

以F(6)為例，遞歸求解過程如下圖所示。

練習：寫一個遞歸程序，輸出1+2+3+…+n。