递归算法基础
在计算机编程应用中,递归算法对解决大多数问题都是十分有效的,主要是因为它能够使算法的描述变得简洁和易于理解,主要有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);
}
}
}
网友评论