• 遞歸函數(shù)
• 棧
• 隊列
• 深度優(yōu)先搜索
• 寬度優(yōu)先搜索

2.1.1 遞歸函數(shù)

在一個函數(shù)中再次調(diào)用該函數(shù)本身的行為叫做遞歸，這樣的函數(shù)被稱為遞歸函數(shù)。
1）階乘函數(shù) int fact(int n)

int fact(int n){
    if(n==1) return 1;
    return fact(n-1)\*n;
}

注意：0！=1，n!=(n-1)!×n。

2）斐波那契數(shù)列 int fib(int n)

int fib(int n){
    if(n<=1){
        return n;
    }
    return fib(n-1)+fib(n-2);
}

注意：指的是這樣一個數(shù)列：0、1、1、2、3、5、8、13、21、…
F(0)=0，F(xiàn)(1)=1，F(xiàn)(n)=F(n-1)+F(n-2) (n≥2，n∈N*)

2.1.2 棧

Stack是支持push和pop兩種操作的數(shù)據(jù)結構。實現(xiàn)的是一種LIFO策略。

2.1.3 隊列

Queue是支持push和pop兩種操作的數(shù)據(jù)結構。實現(xiàn)的是一種FIFO策略。

2.1.4 深度優(yōu)先搜索（DFS）

DFS從某個狀態(tài)開始，不斷地轉(zhuǎn)移狀態(tài)直到無法轉(zhuǎn)移，然后回退到前一步的狀態(tài)，繼續(xù)轉(zhuǎn)移到其他狀態(tài)，如此不斷重復，直至找到最終的解。

1）部分和問題
<pre><code>給定整數(shù)a1、a2、…an，判斷是否可以從中選出若干數(shù)，使它們的和為k。
限制條件：

1. 1 ≤ n ≤ 20
2. -10^8 ≤ ai ≤ 10^8
3. -10^8 ≤ k ≤ 10^8

樣例1：
輸入：
n = 4;
a = {1,2,4,7};
k = 13
輸出：Yes

樣例2：
輸入：
n = 4
a = {1,2,4,7}
k=15
輸出：NO

狀態(tài)轉(zhuǎn)移的順序

//
// Created by Nathan on 15/3/21.
// Copyright (c) 2015年 Nathan. All rights reserved.
//

include <iostream>

using namespace std;
int n,k;
const int MAX = 100000000;
int a[MAX];
int solve(int res ,int i ){
if(i==n) return res==k;
if(solve(res+a[i],i+1)) return true;
if(solve(res,i+1)) return true;
return false;
}
int main(int argc, const char * argv[]) {
cin >> n >> k;
for (int i = 0; i<n; i++) {
cin >> a[i];
}
if(solve(0,0)){
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}</code></pre>
2）Laking Counting
<pre><code>
計算出園子里總共有多少水洼？八連通的積水被認為是連接在一起的。
輸入：
N=10 , M=12
園子如下如：
W . . . . . . . . W W .
. W W W . . . . . W W W
. . . . W W . . . W W .
. . . . . . . . . W W .
. . . . . . . . . W . .
. . W . . . . . . W . .
. W . W . . . . . W W .
W . W . W . . . . . W .
. W . W . . . . . . W .
. . W . . . . . . . W .
代碼如下：
//
// Created by Nathan on 15/3/21.
// Copyright (c) 2015年 Nathan. All rights reserved.
//

include <iostream>

using namespace std;
const int MAX=100;
char field[MAX][MAX];
int M,N;
void dfs(int x,int y){
field[x][y]='.';
for (int dx =-1; dx <= 1; dx++) {
for (int dy =-1; dy <= 1; dy++) {
int nx = dx+x;
int ny = dy+y;
if(field[nx][ny]=='W' && 0<=nx && nx < N && 0<= ny && ny<M) dfs(nx,ny);
}
}
}
int main(int argc, const char * argv[]) {
cin >> N >> M;
for (int i= 0; i<N; i++) {
for (int j = 0; j<M; j++) {
cin >> field[i][j];
}
}
int res = 0;
for (int i = 0; i<N; i++) {
for (int j =0; j<M; j++) {
if(field[i][j]=='W'){
dfs(i,j);
++res;
}
}
}
cout << res << endl;
return 0;
}
</code></pre>

2.1.5 寬度優(yōu)先搜索（BFS）

1）迷宮最短路徑
<pre><code>
輸入：
N,M = 10;

S # # # # # # .

. . . . . . # . . #
. # . # # . # # . #
. # . . . . . . . .

# . # # . # # #

. . . . # . . . . #
. # # # # # # # . #
. . . . # . . . . .
. # # # # . # # # .
. . . . # . . . G #
sx = 0; sy = 1;
gx = 9; gy = 8;
輸出：22
//
// Created by Nathan on 15/3/21.
// Copyright (c) 2015年 Nathan. All rights reserved.
//

include <iostream>

include <queue>

using namespace std;
typedef pair<int,int>P;
queue<P>que;
const int MAX = 100;
const int INF = 10000;
char field[MAX][MAX];
int d[MAX][MAX];
int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int N,M;
int sx,sy;
int gx,gy;
int bfs(){
for (int i = 0 ; i<N; i++) {
for (int j = 0; j<M; j++) {
d[i][j] = INF;
}
}
que.push(P(sx,sy));
d[sx][sy]=0;
while (que.size()) {
P q = que.front();
que.pop();
if(q.first==gx && q.second==gy) break;
for (int i = 0; i<4; i++) {
int nx = dx[i]+q.first;
int ny = dy[i]+q.second;
if(0<=nx && nx<N && 0<=ny && ny<M && field[nx][ny]!='#' && d[nx][ny]==INF){
d[nx][ny] = d[q.first][q.second]+1;
que.push(P(nx,ny));
}
}
}
return d[gx][gy];
}
int main(int argc, const char * argv[]) {
cin >> sx >> sy;
cin >> gx >> gy;
cin >> N >> M;
for (int i = 0 ; i<N; i++) {
for (int j=0; j<M; j++) {
cin >> field[i][j];
}
}
int res = bfs();
cout << res << endl;
return 0;
}</code></pre>