如何理解递归？
前语：不要为了读文章而读文章，一定要带着问题来读文章，勤思考。
作者：刘半仙 来源：http://1t.click/eWx
# 递归是什么?
定义：程序调用自身的编程技巧称为递归。
它分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。
递归使用的是选择结构：if/switch。而for，while，do while使用的是循环结构。
定义不明白不要紧，先思考以下表达式，要怎么写程序来计算呢？
1+2+3....+100=?
很多人第一反应使用for循环来解决：
int sum =0;for (int i = 1; i <= 100; i++) { sum+=i;}System.out.println(sum);//5050 int start =1; int end = 100; int sum =(start+end)*end/2;//首项加末项乘以项数除以二 System.out.println(sum);//5050static int recursion(int n){ if(n==1){//递归出口 return 1; }else{ return n+recursion(n-1); }}通过初体验对比,不难发现以下递归有以下几个要点。
优点：使程序结构更清晰,更简洁,更容易让人理解。
缺点：使用递归调用时，如果过多的调用容易造成java.lang.StackOverflowError即栈溢。
出和程序执行过慢。这是一个潜在Bug和影响程序执行效率问题，需要谨慎使用。对于互联网这种以速度和效率来维护用户量，不得以用递归时，可以把处理的数据放入缓存，或者直接使用迭代等方式来解决。
规律：递归要有出口，不然成了死循环。解出递归的要点在于求出n-1，求出了n-1才能求解出n,这是为什么呢?
# 递归的执行过程
前文对于递归的定义中说，递归分为调用阶段和回退阶段，递归的回退顺序是它调用顺序的逆序。为了理解执行过程，这里配合实例讲解。请思考如何写出它的递归代码：
n!=n*(n-1)*(n-2)...*3*2*1
这里给出数学表达式：
从表达式中可以明显的可以看出：
递归有出口；
递归是选择结构。
递归代码也不难。
它的调用顺序是怎么样的呢？
当你传入5时，方法内会去调用方法factorial（4），然后又调用方法factorial（3）直到factorial（0）=1时开始返回，下面为更详细的图解。
1、调用阶段
2、回退阶段
图中红色箭头为调用阶段，绿色箭头为回退阶段。这就是递归的要点在于求出n-1，求出了n-1才能求解出n，它思想其实和数学中的归纳本质上是相同的。
# 汉诺塔游戏讲解
游戏规则：有三根柱子，最左边的一根柱子从下往上按照大小顺序摞着64片圆盘。需要你借助中间的柱子把左边的所有圆盘移动到最右边的柱子上。并且规定，下面圆盘始终要比上面的大，在三根柱子之间一次只能移动一个圆盘。求出最少移动的次数。
如果要把X柱上得3个圆盘移动到Z柱，步骤如下：
①把X柱最上面的小圆盘移动到Z柱。②再把X柱中间大的圆盘移动到Y柱。③把Z柱上最小的圆盘移动到Y柱上。
这三次操作如图所示：
再加上步骤④⑤⑥⑦，所以3个圆盘至少需要移动7次。如果移动6个圆盘时：
所以，可以推出,当n个从x柱，经由y柱中转，移动到z柱(解出n层汉诺塔时)，有:
当n=0时，不用做任何操作；
当n>0时，
首先,将n-1个盘子从x借助z移动到y
然后,将1个盘子从x移动到z
最后,将在中间y上的n-1个盘子借助x移动到z
为了解出n层汉诺塔，需要先使用n-1层汉诺塔的解法。
从推到过程中我们可以发现：解出递归的要点在于求出n-1，求出了n-1才能求解出n。此外，从数学角度也可以归纳出 0,1,3,7,15,63...表达式为:f(n)=2^n - 1。
现在，我们可以给出代码：
static int t=0;//最少移动次数public static void main(String[] args) { hanio(3,"x","y","z"); System.out.println(t);} static void hanio(int n ,String src,String mid,String dest){ if(n==1){ System.out.println(src+"-->"+dest);//移动过程 t++; }else{ hanio(n-1,src,dest,mid);//将n-1个盘子从x借助z移动到y hanio(1,src,"",dest);//因为中间柱子没用到,所以可以填""或者填mid,然后将最大的盘子从x直接移动到z hanio(n-1,mid,src,dest);//将在中间y柱上的n-1个盘子借助x移动到z }}# 总结和展望
递归对于解决某些问题非常方便（比如递归读取文件路径），也易于理解。虽然用迭代不是不可以实现，只是同样为了解决某些特性问题，写出迭代的代码花费的时间和难度却比递归高。
前文提到，递归和数学中的归纳思想本质上是相同的，都是"将复杂的问题简化"。掌握递归思想的核心就在于"把握结构",因为把握结构是分解整个问题的突破口。
热文推荐