A. 遞歸的概念
是指函數/過程/子程序在運行過程序中直接或間接調用自身而產生的重入現象。
在計算機編程里，遞歸指的是一個過程：函數不斷引用自身，直到引用的對象已知。
使用遞歸解決問題，思路清晰，代碼少。但是在主流高級語言中（如C語言、Pascal語言等）使用遞歸演算法要耗用更多的棧空間，所以在堆棧尺寸受限制時（如嵌入式系統或者內核態編程），應避免採用。所有的遞歸演算法都可以改寫成與之等價的非遞歸演算法。
漢諾塔問題，是常見可用遞歸解決的問題，不過也有非遞歸的解法。
菲波納契數列可用遞歸定義。
以下為求漢諾塔問題的Pascal程序：
procere Hanoi(n:integer;x,y,z:char);
遞歸
begin
if n<>1 then begin
Hanoi(n-1,x,z,y);
writeln(x,n,z);
Hanoi(n-1,y,x,z);
else writeln(x,n,z);
end;
end;
上述程序用接近自然語言的偽代碼可表述如下：
Hanoi 過程 (整型參數n; 字元型參數 x,y,z);
//註：n 代表本步中要處理的盤子數，x,y,z 分別表示 n 號盤子原來所在柱子、經由柱子、目標柱子
開始
如果 n 不為 1 ，那麼：開始
調用 Hanoi 過程 (參數為 n-1,x,z,y);
//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 x 經由柱子 z 移動到柱子 y
輸出 x,n,z; //註：表示將 n 號盤子從 x 移動到 z
調用 Hanoi 過程 (參數為 n-1,y,x,z);
//註：這一步表示用本過程方法將剩餘 n-1 個盤子從柱子 y 經由柱子 x 移動到柱子 z
結束; //以上程序段就完成了把 n 個盤子從柱子 x 經由柱子 y 移動到柱子 z
否則 輸出 x,n,z; //註：若 n 為1 的話本句直接輸出表示將 n 號盤子從 x 移動到 z
遞歸，就是在運行的過程中調用自己。
構成遞歸需具備的條件：
函數嵌套調用過程示例
1. 子問題須與原始問題為同樣的事，且更為簡單；
2. 不能無限制地調用本身，須有個出口，化簡為非遞歸狀況處理。
在數學和計算機科學中，遞歸指由一種（或多種）簡單的基本情況定義的一類對象或方法，並規定其他所有情況都能被還原為其基本情況。
B. 演算法的子集和數問題
回溯演算法設計2008-05-29 10:15 P.M.[實驗目的]
1. 掌握回溯法解題的基本思想；
2. 掌握回溯演算法的設計方法；
3. 針對子集和數問題，熟練掌握回溯遞歸演算法、迭代演算法的設計與實現。
[預習要求]
1. 認真閱讀教材或參考書, 掌握回溯法解題的基本思想, 演算法的抽象控制策略；
2. 了解子集和數問題及解向量的定長和變長狀態空間表示；
3. 針對解向量的定長表示, 設計狀態空間樹節點擴展的規范(限界)函數及實現方法；
4. 分析深度優先擴展狀態空間樹節點或回溯的條件；
5. 分析和設計生成解向量各分量可選值的實現方法；
6. 設計和編制回溯演算法的遞歸和迭代程序。
[參考數據類型或變數]
float s; // 表示有可能抵達答案節點的子路徑上的元素之和；
float r; // 尚未測試的剩餘集合元素之和；
float w[n]; // 存儲原始集合的n個元素, 根據問題實例初始化；
int x[n]; // 定長表示的解向量, 各元素初始值為0；
[參考子程序介面與功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 針對問題實例的遞歸回溯演算法。
void IterativeSubset(int m)
功能: 針對問題實例的迭代回溯演算法。
void InitializeInstanse(void)
功能: 問題實例的初始化函數, 初始化子集和數M , w, x向量, s, r。
[實驗步驟]
1. 錄入、修改並測試你的程序，直至正確為止；
2. 針對問題實例，實錄運行時的輸入、輸出界面；
3. 將你的程序和實錄的界面存檔備用。
[實驗報告要求]
1. 闡述實驗目的和實驗內容；
2. 提交模塊化的實驗程序源代碼；
3. 簡述程序的測試過程，提交實錄的輸入、輸出界面；
4. 鼓勵對實驗內容展開討論，鼓勵提交思考與練習題的代碼和測試結果。
[思考與練習]
1. 試針對解向量的變長表示設計回溯演算法，上機測試正確性。
2. 試針對0/1背包問題設計回溯演算法，比較與子集和數問題的演算法差異。
#include<stdio.h>
#define n 3
float s; /*表示有可能抵達答案節點的子路徑上的元素之和；*/
float r; /*尚未測試的剩餘集合元素之和；*/
float w[n]={2,3,4}; /*存儲原始集合的n個元素, 根據問題實例初始化；*/
int x[n]; /*定長表示的解向量, 各元素初始值為0；*/
int M;
int k;
void RecursiveSubset(float s, float r, int k)/*針對問題實例的遞歸回溯演算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i<n;i++)
printf("%2d",x[i]);
printf("\n");}
else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*針對問題實例的迭代回溯演算法*/
{int i;
for(i=0;i<m;i++) x[i]=2;
for(i=k-1;i<n;i++) r+=w[i];
k=1;
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i<m-1;i++)
x[i]=2;
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i<n;i++)
{printf("%2d",x[i]);}
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*問題實例的初始化函數, 初始化子集和數M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i<n;i++)x[i]=0;
for(i=k-1;i<n;i++) r+=w[i];
for(i=0;i<k-2;i++) s+=x[i]*w[i];
}
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");
C. 遞歸主方法
遞歸的主要方法是什麼？
一、遞歸演算法
遞歸演算法（英語：recursion algorithm）在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。遞歸式方法可以被用於解決很多的計算機科學問題，因此它是計算機科學中十分重要的一個概念。絕大多數編程語言支持函數的自調用，在這些語言中函數可以通過調用自身來進行遞歸。計算理論可以證明遞歸的作用可以完全取代循環，因此在很多函數編程語言（如Scheme）中習慣用遞歸來實現循環。
二、遞歸程序
在支持自調的編程語言中，遞歸可以通過簡單的函數調用來完成，如計算階乘的程序在數學上可以定義為：
這一程序在Scheme語言中可以寫作：
1
(define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))
不動點組合子
即使一個編程語言不支持自調用，如果在這語言中函數是第一類對象（即可以在運行期創建並作為變數處理），遞歸可以通過不動點組合子（英語：Fixed-point combinator）來產生。以下Scheme程序沒有用到自調用，但是利用了一個叫做Z 運算元（英語：Z combinator）的不動點組合子，因此同樣能達到遞歸的目的。
1
(define Z (lambda (f) ((lambda (recur) (f (lambda arg (apply (recur recur) arg)))) (lambda (recur) (f (lambda arg (apply (recur recur) arg)))))))(define fact (Z (lambda (f) (lambda (n) (if (<= n 0) 1 (* n (f (- n 1))))))))
這一程序思路是，既然在這里函數不能調用其自身，我們可以用 Z 組合子應用(application)這個函數後得到的函數再應用需計算的參數。
尾部遞歸
尾部遞歸是指遞歸函數在調用自身後直接傳回其值，而不對其再加運算。尾部遞歸與循環是等價的，而且在一些語言（如Scheme中）可以被優化為循環指令。 因此，在這些語言中尾部遞歸不會佔用調用堆棧空間。以下Scheme程序同樣計算一個數字的階乘，但是使用尾部遞歸：
1
(define (factorial n) (define (iter proct counter) (if (> counter n) proct (iter (* counter proct) (+ counter 1)))) (iter 1 1))
三、能夠解決的問題
數據的定義是按遞歸定義的。如Fibonacci函數。
問題解法按遞歸演算法實現。如Hanoi問題。
數據的結構形式是按遞歸定義的。如二叉樹、廣義表等。
四、遞歸數據
數據類型可以通過遞歸來進行定義，比如一個簡單的遞歸定義為自然數的定義：「一個自然數或等於0，或等於另一個自然數加上1」。Haskell中可以定義鏈表為：
1
data ListOfStrings = EmptyList | Cons String ListOfStrings
這一定義相當於宣告「一個鏈表或是空串列，或是一個鏈表之前加上一個字元串」。可以看出所有鏈表都可以通過這一遞歸定義來達到。
D. python-027-遞歸-求序列最大值、計算第n個調和數、轉換字元到整數
遞歸，emmmmmmm，擁有一種魅力，接近人的立即思維，容易理解，又不容易理解。
遞歸演算法的優點： 它使我們能夠簡潔地利用重復結構呈現諸多問題。通過使演算法描述以遞歸的方式利用重復結構，我們經常可以避開復雜的案例分析和嵌套循環。這種演算法會得出可讀性更強的演算法描述，而且十分有效。
但是 ，遞歸的使用要根據相應的成本來看，每次遞歸python解釋器都會給一個空間來記錄函數活動狀態。但是有時候內存成本很高，有時候將遞歸演算法轉為非遞歸演算法是一種好辦法。
當然我們可以換解釋器、使用堆棧數據結構等方法，來管理遞歸的自身嵌套，減小儲存的活動信息，來減小內存消耗。
最近演算法學到了遞歸這一塊，寫了三個課後習題：
給一個序列S，其中包含n個元素，用遞歸查找其最大值。
輸出：
調和數：Hn = 1 + 1/2 + 1/3 + ··· + 1/n
輸出：
例如："12345"<class 'str'> 轉換為12345<class 'int'>
輸出：
遞歸分為線性遞歸、二路遞歸、多路遞歸。