遞迴的定義

在定義一個過程或函式時出現呼叫本過程或本函式的成分，稱之為遞迴。

若呼叫自身，稱之為直接遞迴。

若過程或函式A呼叫過程或函式B，而B又呼叫A，稱之為間接遞迴。

如果一個遞迴過程或遞迴函式中遞迴呼叫語句是最後一條執行語句，稱為尾遞迴。

以下是求n!（n為正整數）的遞迴函式。它屬於什麼型別的遞迴。

解：直接遞迴函式。又由於遞迴呼叫是最後一條語句，所以它又屬於尾遞迴。

遞迴演算法通常通常把一個大的複雜問題層層轉化為一個或多個與原問題相似的規模較小的問題來求解。

遞迴策略只需少量的程式碼就可以描述出解題過程所需要的多次重複計算，大大減少了演算法的程式碼量。

一般來說，能夠用遞迴解決的問題應該滿足以下3個條件：

需要解決的問題可以轉化為一個或多個子問題來求解，而這些子問題的求解方法與原問題完全相同，只是在數量規模上不同。

遞迴呼叫的次數必須是有限的。

必須有結束遞迴的條件來終止遞迴。

何時使用遞迴

有許多數學公式、數列等的定義是遞迴的。例如，求n!和Fibonacci（斐波那契）數列等。

資料結構是遞迴的

有些資料結構是遞迴的。如單鏈表就是一種遞迴資料結構。

求一個不帶頭結點單鏈表p中所有data成員（假設為int型）之和。

問題的求解方法是遞迴的

設Hanoi(n，x，y，z)表示將n個碟片從x塔座藉助y塔座移動到z塔座上

一般地，一個遞迴模型是由遞迴出口和遞迴體兩部分組成。

遞迴出口確定遞迴到何時結束，即指出明確的遞迴結束條件。

遞迴體確定遞迴求解時的遞推關係。

遞迴出口的一般格式如下：

遞迴體的一般格式如下：

遞迴與數學歸納法

採用數學歸納法證明1+2+…+n=n(n+1)/2

遞迴的執行過程

遇到遞迴出口發生“質變”，原遞迴問題便轉化成可以直接求解的問題。

求值過程：

例如：求5!。

系統內部如何執行遞迴演算法

一個遞迴函式的呼叫過程類似於多個函式的巢狀的呼叫，只不過呼叫函式和被呼叫函式是同一個函式。

為了保證遞迴函式的正確執行，系統需設立一個工作棧。

（1）執行開始時，首先為遞迴呼叫建立一個工作棧，其結構包括值參、區域性變數和返回地址。

（2）每次執行遞迴呼叫之前，把遞迴函式的值參和區域性變數的當前值以及呼叫後的返回地址進棧。

（3）每次遞迴呼叫結束後，將棧頂元素出棧，使相應的值參和區域性變數恢復為呼叫前的值，然後轉向返回地址指定的位置繼續執行。

例如，有以下程式段：

程式執行時使用一個棧來儲存呼叫過程的資訊，這些資訊用main()、S(0)和S(1)表示，那麼自棧底到棧頂儲存的資訊的順序是怎麼樣呢？

用遞迴演算法的形參值表示狀態，由於遞迴演算法執行中系統棧儲存了遞迴呼叫的值參、區域性變數和返回地址。

所以在遞迴演算法中一次遞迴呼叫後會自動恢復該次遞迴呼叫前的狀態。

遞迴演算法的時空分析

遞迴演算法執行過程不同於非遞迴演算法，所以其時空分析也不同於非遞迴演算法。

非遞迴演算法分析是定長時空分析。

遞迴演算法分析就是變長時空分析。

遞迴演算法的時間分析

遞迴演算法的空間分析

遞迴演算法分析

遞迴演算法設計的步驟

設計求解問題的遞迴模型。

轉換成對應的遞迴演算法。

　求遞迴模型的步驟如下：

採用遞迴演算法求整數陣列a[0..n-1]中的最小值。

基於遞迴資料結構的遞迴演算法設計

假設有一個不帶頭結點的單鏈表p，完成以下兩個演算法設計：

（1）設計一個演算法正向輸出所有結點值。

（2）設計一個演算法反向輸出所有結點值。

(1)正向輸出

(2)反向輸出

基於歸納方法的遞迴演算法設計

透過對求解問題的分析歸納來轉換成遞迴方法求解（如皇后問題等）。

關鍵是對問題本身進行分析，確定大、小問題解之間的關係，構造合理的遞迴體，而其中最重要的又是假設出“合理”的小問題。

例子：若演算法pow(x，n)用於計算xn（n為大於1的整數）。完成以下任務：

（1）採用遞迴方法設計pow(x，n)演算法。

（2）問執行pow(x，10)發生幾次遞迴呼叫？求pow(x,n)對應的演算法複雜度是多少？

例子：建立一個n階螺旋矩陣並輸出。例如，n=4時的螺旋矩陣如下：

答案：

例子：採用遞迴演算法求解迷宮問題，並輸出從入口到出口的所有迷宮路徑。