递归精讲篇

递归的构成条件：

1、一个大问题可以分解成多个子问题
2、子问题与大问题的解决方式完全一样，只是规模不同
3、子问题具有递归终止条件
计算机上的递归与方法栈密不可分。

编写递归代码的关键是：寻找递推公式和终止条件。

递归的一个经典例子上台阶：

有n个台阶，你一次只能迈出一步，每步可跨一个台阶或两个台阶，问一共有多少种走法？
分析：
1、分解子问题；
假设有f(n)种走法，每一步只有两种情况，迈一个台阶或者两个台阶。第一步跨一级阶梯，那么就剩下f(n-1)种走法；如果第一步是跨两个台阶，那么就剩下f(n-2)走法。
递推公式：f(n)=f(n-1)+f(n-2)

2、寻找终止条件。
最后一步也是只有两种情况，要么以跨一台阶结束，要么以跨两台阶结束。不存在第三种情况。

f(1)=1这个是终止条件么？看着像，一级台阶只有一种走法，无法再分解(分解就成：f(1)=f(0)+f(-1)了，不合逻辑)。但是往前一推，f(2)=f(1)+f(0)，f(0)是无需求解，也无意义的(0个台阶0种走法)，f(1)是终止条件之一。

f(2)=2这个是终止条件么？看着像，两级台阶只有两种走法，无法再分解(分解就成：f(2)=f(1)+f(0)了，不合逻辑)。往前一推，f(3)=f(2)+f(1),其中f(2)与f(1）都是不可分解且合理的，f(2)也是终止条件之一。

f(3)=f(2)+f(1),即f(3)是可分解的，不是终止条件，毕。

把递推公式与终止条件放到一起：

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

翻译成java代码：

int f(n){
  if(n==1){
    return 1;//一级台阶只有一种走法：[1]
    }
  if(n==2){
    return 2;//两级台阶只有2种走法：[1，1]或[2]
  }
  return f(n-1)+f(n-2);
}

PS：
不要试图用人脑去分解递归的每一个步骤！
不要试图用人脑去分解递归的每一个步骤！
不要试图用人脑去分解递归的每一个步骤！
重要的事情说三遍。

试图弄成整个递归过程的做法实际上是一种思维误区，自己给自己制造理解障碍。

如果一个问题母可以分解成多个子问题，只需关注母问题与子问题这两层的关系，不需要一层层地考虑子问题与子问题的关系，屏蔽递归细节，总结递推公式，这才是编写递归代码的正确方式。