递归算法基础
在计算机编程应用中，递归算法对解决大多数问题都是十分有效的，主要是因为它能够使算法的描述变得简洁和易于理解，主要有3个特点。
- 递归过程一般通过函数或子过程来实现
- 递归算法在函数或子过程的内部，直接或间接地调用自己的算法。
- 递归算法实际上是把问题转化成规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。
使用递归算法时，应该注意以下4点：
- 递归是在过程或者函数中调用自身的过程
- 在使用递归策略时，必须有一个明确的递归结束条件，称之为递归出口
- 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡使用
- 在递归调用过程中，系统通过栈来存储每一层的返回点和局部量。如果递归次数过多，很容易造成栈溢出(StackOverflowError)
例如：
public class stack {
private static int index = 1;
public static void main(String[] args) {
try {
test();
} catch (StackOverflowError e) {
System.out.println(index);
e.printStackTrace();
}
}
public static void test() {
index++;
test();
}
}
通过递归不断地去调用自身，超过系统的栈的深度就会直接报错
接下来通过汉诺塔的例子具体讲解一下递归过程
首先什么是汉诺塔呢？
在世界中心贝拿勒斯（在印度北部）的圣庙里，一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候，在其中一根针上从下到上地穿好了由大到小的64片金片，这就是所谓的汉诺塔。不论白天黑夜，总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片，不管在哪根针上，小片必须在大片上面。僧侣们预言，当所有的金片都从梵天穿好的那根针上移到另外一根针上时，世界就将在一声霹雳中消灭，而梵塔、庙宇和众生也都将同归于尽。
okay，我们的目标是要把第一个柱子上的64片移到第三个柱子上面去
- 首先第一轮可以把前63片移到第二个柱子上面去，再把第64片移到第三个柱子上面去，再把第二个柱子上面的63片移到第三个柱子上面
- 那么，第二轮的问题是怎么把前63片移到第二个柱子，可以先把前62片移到第三个柱子上面去，再把第63片移到第二个柱子上面去，再把第三个柱子上面的62片移到第二个柱子上面
- .......
- 到了最上面一片只需要将第一片移开，把第二片移到另一个空柱子，再把第一片移到第二片上面去，完成整个操作(第一片移到哪个柱子取决于你的片数的奇偶)
这样就形成了递归，在你调用move(n,a,b,c)的时候，只需要让n-1个片移到b上面去(move(n-1,a,c,b))，再把第n个片移到c，紧接着把b上面的n-1个片移到c上面去(move(n-1,b,a,c))，就可以完成整个操作。
从结果上面来看，需要搬移的次数为2^n - 1
public class HanoiTest {
private static int count;
public static void main(String[] args) {
move(64,'a','b','c');
System.out.println(count);
}
private static void move(int n,int a,int b,int c) {
if (n == 1) {
count++;
System.out.println((char)a +"-->"+ (char)c);
} else {
move(n-1,a,c,b);
count++;
System.out.println((char)a +"-->"+ (char)c);
move(n-1,b,a,c);
}
}
}
