1. 遞歸(Recursion)
1.1 概念
遞歸是一種直接或者間接調(diào)用自身函數(shù)。
1.2 本質(zhì)
把問題分解成規(guī)牧辈t？s小的同類問題的子問題
遞歸就是函數(shù)的“套娃”
1.3 套路
- 確定遞歸公式
- 確定邊界條件
1.4 練習
- 遞歸打印
1~10 - 數(shù)組求和
- 階乘
- 打印第
n個斐波那契數(shù)列
使用遞歸模擬
for循環(huán)(自增的i和不停的調(diào)用)辙纬。
在第一個月有一對剛出生的小兔子裳凸，在第二個月小兔子變成大兔子并開始懷孕犀盟，第三個月大兔子會生下一對小兔子螃征，并且以后每個月都會生下一對小兔子俊性。 如果每對兔子都經(jīng)歷這樣的出生略步、成熟、生育的過程定页，并且兔子永遠不死趟薄，那么兔子的總數(shù)是如何變化的？
1.5 原理解析
小知識
德羅斯特效應(Droste effect)是遞歸的一種視覺形式典徊，是指一張圖片的某個部分與整張圖片相同杭煎，如此產(chǎn)生無限循環(huán)。
2. 迭代
2.1 概念
迭代（輾轉(zhuǎn)法）是一種不斷用變量的舊值遞推新值的過程卒落。
2.2 本質(zhì)
迭代很多時候就是使用循環(huán)實現(xiàn)羡铲。
2.3 套路
int sum(int n ) {
int sum =0;
for(int i = 1 ; i <= n;i++) sum+=n;//求解1~n的和
return sum;
}
- 確定迭代變量：確定一個直接或間接地不斷由舊值推斷新值的變量，如
sum儡毕。 - 建立迭代關(guān)系式：從變量的舊值推斷到新值的公式也切，如
。
- 對迭代過程進行控制：迭代不可能無限循環(huán)下去，需要對何時退出迭代進行控制雷恃，如
i=>n退出循環(huán)疆股。
2.4 練習
- 遞歸打印
1~10 - 數(shù)組求和
- 階乘
- 打印第
n個斐波那契數(shù)列
3. 遞歸與迭代比較
3.1 遞歸可能比較耗內(nèi)存
實現(xiàn)函數(shù)printN(int n),打印從1到n的所有整數(shù)。
#include <stdio.h>
#include <stdlib.h>
#ifndef RECURSION
void printN(int n){
for(int i=1;i<=n;++i){
printf("%d\n",i);
}
}
#else
void printN(int n){
if(0 != n) {
printN(n-1);
printf("%d\n",n);
}
}
#endif
int main(int argc,char** argv) {
if(argc != 2){
printf("usage:%s <num>\n",argv[0]);
return 1;
}
printN(atoi(argv[1]));
return 0;
}
編譯執(zhí)行printN(int n)函數(shù)循環(huán)實現(xiàn)
gcc test.c && ./a.out 1000000
編譯執(zhí)行printN(int n)函數(shù)遞歸實現(xiàn)
gcc -DRECURSION test.c && ./a.out 1000000
3.2 遞歸可能比較效率低
斐波那契數(shù)列
- 遞歸
#include <stdio.h>
#include <stdlib.h>
#ifndef RECURSION
long long Fibonacci(int n) {
if(n < 1) return 0;
if(1 == n || 2 == n) return 1;
return Fibonacci(n-1) + Fibonacci(n-2);
}
#else
long long Fibonacci(int n) {
if(n<1) return 0;
long long a = 0;
long long b = 1;
for(int i=2;i<=n;i++){
b += a;
a = b - a;
}
return b;
}
#endif
int main(int argc,char** argv) {
if(argc != 2){
printf("usage:%s <num>\n",argv[0]);
return 1;
}
printf("%lld\n",Fibonacci(atoi(argv[1])));
return 0;
}
編譯執(zhí)行Fibonacci(int n)函數(shù)循環(huán)實現(xiàn)
gcc test.c && ./a.out 45
編譯執(zhí)行Fibonacci(int n)函數(shù)遞歸實現(xiàn)
gcc -DRECURSION test.c && ./a.out 45
命令time可以測量程序執(zhí)行的時間褂萧。
練習：遞歸打印九九乘法表
void PrintCol(int r,int c){
if(0==c) return;
PrintCol(r,c-1);
printf("%d*%d=%2d ",r,c,r*c);
}
void PrintRow(int r){
if(0==r) return;
PrintRow(r-1);
PrintCol(r,r);
printf("\n");
}
禁止套娃
4. 動態(tài)規(guī)劃
解決遞歸性能問題的一種方法押桃。
70. 爬樓梯
- 遞歸：樓頂開始思考，自頂而下
class Solution {
public:
int climbStairs(int n) {
if(1==n||2==n) return n;
return climbStairs(n-1)+climbStairs(n-2);
}
};
遞歸超時导犹，因為存在大量的重復計算唱凯。
- 動態(tài)規(guī)劃之備忘錄/記憶化
使用數(shù)組記錄計算過程中的數(shù)值，避免重復計算谎痢。
class Solution {
public:
vector<int> dp; // 動態(tài)規(guī)劃：備忘錄/記憶化
int climbStairs(int n) {
if(dp.empty()) dp.resize(n+1);
if(1==n||2==n) return n;
if(0==dp[n]) dp[n] = climbStairs(n-1)+climbStairs(n-2);// 減少重復遞歸計算
return dp[n];
}
};
- 動態(tài)規(guī)劃之自底而上
樓底開始思考磕昼，自底而上，迭代方式解決問題节猿。
class Solution {
public:
int climbStairs(int n) {
if(1==n||2==n) return n;
int prev = 1; // 臺階1
int curr = 2; // 臺階2
for(int i=3;i<=n;++i){
int res = prev + curr;
prev =curr;
curr = res;
}
return curr;
}
};
練習
- 鏈表的順序和逆序打印數(shù)據(jù)
- 鏈表的反序
