引语：

本篇文章从迭代，递归，再到深搜，由浅入深结合例题介绍。如果是零基础的，建议从头看完，这样到后面更好理解，如果递归学的较好的话也可以跳过前面的递归部分。

在各种算法竞赛或者面试中，总会有一些题目要求我们给出某个问题的各种方案以及方案的个数，对于数量级比较小的题目，我们可以采用枚举之类的暴力解法，但是对于数量级到达n的三次方及以上的题目甚至是阶乘级的题目就要小心了，因为暴力求解很可能超时。

所以，我们可以用试探性解法，当某一条支路提前确定走不通的时候，我们就不必继续向下进行了。也可以理解为“不撞南墙不回头”，或者“先把一条路走到黑”。

虽然看起来比暴力枚举更快一点，但是《算法竞赛入门经典》这本书将这种方法一并归到“暴力求解法”这一章。

回顾

首先，我想先从“逐步生成结果”开始讲起。

刚开始学C语言的时候，我们会学“斐波那契数列”，这就是典型的“逐步生成”思想，也可以理解为迭代。

我相信斐波那契大家肯定很熟悉了，这里就不在介绍了。

解决简单情况下的问题：上楼梯

题意：有一个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶，2阶，3阶。

请实现一个方法，计算小孩有多少种上楼梯的方式。

为了防止溢出，请将结果Mod1000000007。 给定一个正整数，请返回一个数，代表上楼的方式数。保证n小于等于100000.

由题意，我们可以做出如下图所示的推理：

递推：

#include<stdio.h>
#define mod 1000000007
int main(){
  int x1 = 1, x2 = 2, x3 = 4, n;
  long long ans = 0;
  scanf("%d",&n);
  if(n < 0) ans = 0;
  else if(n == 0 || n == 1) ans = x1;
  else if(n == 2) ans = x2;
  else if(n == 3) ans = x3;
  for(int i = 4; i <= n; i++){
    int t = x1;
    x1 = x2;  x2 = x3;
    x3 = ((x1+x2)%mod+t)%mod;
    ans = x3;
  } 
  printf("%d\n",ans);
  return 0;
}

递归：

long f1(int n){
  if(n < 0) return 0;
  if(n == 0 || n == 1) return 1;
  if(n == 2) return 2;
  return f1(n-1)%mod + f1(n-2)%mod + f1(n-3)%mod;
}

如果大家数学基础比较好，也可以利用递推公式，直接得出封闭解。由于我数学推理不是很好，在这里就不展示了。

推广到稍微复杂的问题：机器人走方格

有一个X*Y的网格，一个机器人只能走格点且只能向右或向下走，要从左上角走到右下角。

请设计一个算法，计算机器人有多少种走法。

给定两个正整数int x,int y，请返回机器人的走法数目。

保证x＋y小于等于12。
由题意我们可以推出：

• 当x或者y为1时，走法都是1种。
• 当x或者y为2，另一个为1时，也就是(1,2)或者(2,1)，走法也都是1种。
• 当x和y都为2时，走法是两种 ……

顺着思路往下想，我们可以画出这样一幅示意图：

从这幅图我们可以发现：

在x+y>=3时，当前状态的解都为(x-1,y)状态的解和(x,y-1)的解的和
也就是f(x,y)=f(x-1,y)+f(x,y-1)
因为在任何一种状态，我们都有两种选择，下或者右，如果现在向下走，那么下一种状态的解即为(x,y-1)的解，如果向右，那么下一种状态为(x-1,y)的解。

所以，我们同样可以用递推或者递归来写代码~

递推：

建立一个二维数组存放每一个状态对应的解，逐步迭代得到所有解

#include<stdio.h>
int solve1(int x, int y){
  int a[x+1][y+1];
  for(int i = 1; i <= x; i++) a[i][1] = 1;//当x或y为1时，解法都是一种
  for(int i = i; i <= y; i++) a[1][i] = 1;
  for(int i = 2; i <= x; i++){
    for(int j = 2; j <= y; j++){
      a[i][j] = a[i-1][j]+a[i][j-1];  //利用递推关系迭代出所有的解
    }
  }
  return a[x][y];
} 
int main(){
  int x,y;
  scanf("%d%d",&x,&y);
  printf("%d\n",solve1(x,y));
  return 0;
}

递归：

int solve2(int x, int y){
  if(x == 0 || y == 0 || x == 1 || y == 1) return 1;
  return solve2(x-1,y)+solve2(x,y-1);
}

由以上两道例题我们发现，递推和递归都是对于需要迭代问题的解法

区别在于：递推是正着思考正着写，递归是正着思考倒着写

递归对于这类问题的思考的锻炼是非常有帮助的。

还有一道更难一点的题：硬币表示（点击阅读我的另一篇文章）