递归（粗解）

递归，要是简单理解它，可以说不难，就是一个递出去，拿回来的过程，拿一个实际生活里面的例子来说：

周末你带着女朋友去电影院看电影，女朋友问你，咱们现在坐在第几排啊？电影院里面太黑了，看不清，没法数，现在你怎么办？

别忘了你是程序员，这个可难不倒你，递归就开始排上用场了。于是你就问前面一排的人他是第几排，你想只要在他的数字上加一，就知道自己在哪一排了。但是，前面的人也看不清啊，所以他也问他前面的人。就这样一排一排往前问，直到问到第一排的人，说我在第一排，然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排，于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程，去的过程叫“递”，回来的过程叫“归”。基本上，所有的递归问题都可以用递推公式来表示。

就上面那个过程，递归程序可以写成：

f(n) = f(n-1)+1

这就是一个简单的递归概念，而递归，也就是这么一个概念。

写递归程序，一定要注意终止条件。

下面给出一个递归程序的模板：

public void recur(int level,int param) {

// terminator 终止条件

    if (level >Max) {

return;

}

// process 逻辑执行

    process(level, param);

// drill down 到下一层

    recur(level +1, param);

// restore data 有可能存储一些数据

}

可以看到，一共四个部分，分别是 1：递归终止条件 2：递归执行逻辑 3：进入下一层 4：数据清除，存储（可选） 。最重要的，就是要确定递归终止条件，否则就会产生无限递归，那么服务器就会崩溃。

写递归程序时，我没要注意一些点：

1：不要进行人肉递归，即我们用人脑来一步步递归，或者画递归状态图。

2：找最近重复子问题，递归可以解决的，就是这种包含重复子问题的问题，这种重复，说的是，除了要处理的数据不一样，他们的梳理过程都是一样的，就像上面那个问题，每一个人要知道自己的位置，就要向前面一个人去问。

3：数学归纳法，这个就是帮助我找到最近重复子问题。我们验证第一排的人知道自己的位置，第二个人向第一个人，就+1，第三个人向第二个人，在第二个人的基础上+1，我们就可以归纳得出这么一共公式，f(n) = f(n-1)+1，这就帮我们找到了最近重复子问题。

那我们拿f(n) = f(n-1)+1这个公式来写一共递归，运用上面的递归模板。

public int test(int n) {

// terminator

    if (n ==1) {

return 1;

}

// process

// drill down

    return test(n -1) +1;

}

我们将drill down 和 process放在一起写了，因为上一个的结果就是下一个的值。

再来看一个小问题：

假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？

那我们也是找重复子问题，使用数学归纳法，上一个台阶只能 是1，上两个台阶可以是1，1，也可以是2，所有f(2)=2,f(1)=1,那么上三个台阶就是1，1，1； 1，2； 2，1，一共f(3)=3,归纳一下，上3级台阶，可以在上第二层的时候上1，也可以是在上第1层的时候上2，所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：

f(n) = f(n-1)+f(n-2)

那么使用程序也就可以很简单的求出来了，先写出递归终止条件：

int f(int n) {

  if (n ==1)return 1;

  if (n ==2)return 2;

  return f(n -1) + f(n -2);

}

写递归程序，一定切忌人肉递归，这样是写不出来的，我们要做的就是将问题抽象化，抽象成一共表达式，然后就可以轻松写出来。