本文是個(gè)人學(xué)習(xí)筆記，素材來自青島大學(xué)王卓老師的教學(xué)視頻。
一方面用于學(xué)習(xí)記錄與分享，
另一方面是想讓更多的人看到這么好的《數(shù)據(jù)結(jié)構(gòu)與算法》的學(xué)習(xí)視頻。
如有侵權(quán)，請(qǐng)留言作刪文處理。
課程視頻鏈接：
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)–第05周11–3.4棧和遞歸
?? 【W(wǎng)eek05】11_棧與遞歸
遞歸的定義
(1) 若一個(gè)對(duì)象部分地包含它自己，或用它自己給自己定義，則稱這個(gè)對(duì)象是遞歸的。
(2) 若一個(gè)過程直接或間接地調(diào)用自己，則稱這個(gè)過程是遞歸的過程。
例如：遞歸求 n 的階乘
long Fact(long n){
if(n == 0)
return 1;
else
return (n * Fact(n-1));
}
以下三種情況嘗嘗用到遞歸方法
(1) 遞歸定義的數(shù)學(xué)函數(shù)
階乘函數(shù)
2 階 Fibonaci 數(shù)列
(2) 具有遞歸特性的數(shù)據(jù)結(jié)構(gòu)
(3) 可遞歸求解的問題
迷宮問題
Hanoi 塔問題
遞歸問題——用分治法求解
分治法
對(duì)于一個(gè)較為復(fù)雜的問題，能夠分解成幾個(gè)相對(duì)簡單的且解法相同或類似的子問題來求解
必備的三個(gè)條件
(1) 能夠?qū)⒁粋€(gè)問題轉(zhuǎn)變?yōu)橐粋€(gè)新問題，且新問題與原問題的解法相同或類同，不同的僅是處理的對(duì)象，且這些處理對(duì)象是變化且有規(guī)律的
(2) 可以通過上述轉(zhuǎn)化而使問題簡化
(3) 必須有一個(gè)明確的遞歸出口，或稱遞歸的邊界
分治法求解遞歸問題算法的一般形式
void p(參數(shù)表){
if(遞歸結(jié)束條件)
可直接求解步驟; // -- 基本項(xiàng)
else
p(較小的參數(shù)); // -- 歸納項(xiàng)
}
例如
long Fact(long n){
if(n == 0)
return 1; // -- 基本項(xiàng)
else
return (n * Fact(n-1)); // -- 歸納項(xiàng)
}
函數(shù)調(diào)用過程
調(diào)用前，系統(tǒng)完成：
(1) 將實(shí)參，返回地址等傳遞給被調(diào)用函數(shù)
(2) 為被調(diào)用函數(shù)的局部變量分配存儲(chǔ)區(qū)
(3) 將控制轉(zhuǎn)移到被調(diào)用函數(shù)的入口
調(diào)用后，系統(tǒng)完成：
(1) 保存被調(diào)用函數(shù)的計(jì)算結(jié)果
(2) 釋放被調(diào)用函數(shù)的數(shù)據(jù)區(qū)
(3) 依照被調(diào)用函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)
當(dāng)多個(gè)函數(shù)構(gòu)成嵌套調(diào)用時(shí)：
int main(void){
...;
y = fact(3);
...;
}
double fact(int n){
...;
z = mypow(3.5, 2);
...;
}
double mppow(double x, int n){
...;
}
遵循后調(diào)用的先返回
求解階乘 n ! 的過程
long Fact(long n){
if(n == 0)
return 1;
else
return (n * Fact(n-1));
}
遞歸函數(shù)調(diào)用的實(shí)現(xiàn)
進(jìn)行 fact(4) 調(diào)用的系統(tǒng)棧的變化狀態(tài)
遞歸的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：結(jié)構(gòu)清晰，程序易讀
缺點(diǎn)：每次調(diào)用要生成工作記錄，保存狀態(tài)信息，入棧；返回時(shí)要出棧，恢復(fù)狀態(tài)信息。時(shí)間開銷大。
遞歸 -> 非遞歸
方法1：尾遞歸、單向遞歸 -> 循環(huán)結(jié)構(gòu)
方法2：自用棧模擬系統(tǒng)的運(yùn)行時(shí)棧
尾遞歸 -> 循環(huán)結(jié)構(gòu)
long Fact(long n){
if(n == 0)
return 1;
else
return (n * Fact(n-1));
}
轉(zhuǎn)換為循環(huán)
long Fact(long n){
t = 1;
for(int i=1; i<n; i++){
t = t*i;
}
return t;
}
單向遞歸 -> 循環(huán)結(jié)構(gòu)
雖然有一處以上的遞歸調(diào)用語句，但各次遞歸調(diào)用語句的參數(shù)只和主調(diào)函數(shù)有關(guān)，相互之間參數(shù)無關(guān)，
并且這些遞歸調(diào)用語句處于算法的最后。
// Fibonacci 數(shù)列
long Fib(long n){
if(n == 1 || n == 2)
return 1;
else
return (Fib(n-1) + Fib(n-2));
}
轉(zhuǎn)換為
// Fibonacci 數(shù)列
long Fib(long n){
if(n == 1 || n == 2)
return 1;
else {
t1 = 1;
t2 = 1;
for(i=3; i<n; i++){
t3 = t1 + t2;
t1 = t2;
t2 = t3;
}
return t3;
}
}
借助棧改寫遞歸
(1) 遞歸程序在執(zhí)行時(shí)，需要系統(tǒng)提供棧來實(shí)現(xiàn)
(2) 仿照遞歸算法執(zhí)行過程中遞歸工作棧的狀態(tài)變化可寫出相應(yīng)的非遞歸程序
(3) 改寫后的非遞歸算法與原來的遞歸算法相比，結(jié)構(gòu)不夠清晰，可讀性較差，有的還需要經(jīng)過一系列優(yōu)化
了解內(nèi)容
借助棧改寫遞歸的方法
(1) 設(shè)置一個(gè)工作棧存放遞歸工作記錄 （包括實(shí)參、返回地址及局部變量等）。
(2) 進(jìn)入非遞歸調(diào)用入口 （即被調(diào)用程序開始處）將調(diào)用程序傳來的實(shí)在參數(shù)和返回地址入棧（遞歸程序不可以作為主程序，因而可認(rèn)為初始是被某個(gè)調(diào)用程序調(diào)用）。
(3) 進(jìn)入遞歸調(diào)用入口: 當(dāng)不滿足遞歸結(jié)束條件時(shí)，逐層遞歸，將實(shí)參、返回地址及局部變量入棧，這一過程可用循環(huán)語句來實(shí)現(xiàn)一模擬遞歸分解的過程。
(4) 遞歸結(jié)束條件滿足，將到達(dá)遞歸出口的給定常數(shù)作為當(dāng)前的函數(shù)值。文章來源：http://www.zghlxwxcb.cn/news/detail-565611.html
(5) 返回處理: 在棧不空的情況下，反復(fù)退出棧頂記錄，根據(jù)記錄中的返回地址進(jìn)行題意規(guī)定的操作，即逐層計(jì)算當(dāng)前函數(shù)值，直至?？諡橹挂荒M遞歸求值過程。文章來源地址http://www.zghlxwxcb.cn/news/detail-565611.html
到了這里，關(guān)于青島大學(xué)_王卓老師【數(shù)據(jù)結(jié)構(gòu)與算法】Week05_11_棧與遞歸_學(xué)習(xí)筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
