• 递归函数
• 栈
• 队列
• 深度优先搜索
• 宽度优先搜索

---

2.1.1 递归函数

在一个函数中再次调用该函数本身的行为叫做递归，这样的函数被称为递归函数。
1）阶乘函数 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）斐波那契数列 int fib(int n)

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

注意：指的是这样一个数列：0、1、1、2、3、5、8、13、21、…
F(0)=0，F(1)=1，F(n)=F(n-1)+F(n-2) (n≥2，n∈N*)

2.1.2 栈

Stack是支持push和pop两种操作的数据结构。实现的是一种LIFO策略。

2.1.3 队列

Queue是支持push和pop两种操作的数据结构。实现的是一种FIFO策略。

2.1.4 深度优先搜索（DFS）

DFS从某个状态开始，不断地转移状态直到无法转移，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直至找到最终的解。

1）部分和问题
<pre><code>给定整数a1、a2、…an，判断是否可以从中选出若干数，使它们的和为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

状态转移的顺序

//
// 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 宽度优先搜索（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>