递归(recursive)算法是一种循环调用自身来解决问题的思想,这是一中比较神奇的方法,你只要能口述循环调用过程,然后设定好基础情况(什么时候开始、什么时候结束),基本根据描述就可以将思路转换成代码,递归算法有以下条件组成:
1、递归开始和结束的基本条件(base case)
2、每次执行需要循环调用自己(也就是找出递归方程),每次调用自己时,执行内容都要向基本条件靠拢,直至满足并跳出基本条件
所以递归定义很重要的一点就是要定义好跳出递归的基本条件,否则极易引起死循环,进去后就出不来,拿一个最简单的故事作为例子来说:
从前有个庙,庙里有个老和尚和一个小和尚,老和尚对小和尚说:从前有个庙,庙里有个老和尚和一个小和尚,老和尚对小和尚说......
这个故事也是一个递归,但是是一个死的递归,因为没有结束的基本条件,故事开始后老和尚会一直重复将这个故事,结果可想而知,如果是
人的话,则老和尚会被累死故事才能结束,如果是计算机,则程序爆掉了执行才能结束,但是如果有结束条件的话就可以避免这种情况发生,比如老和尚
事先对小和尚说好,这个故事只能讲两遍,那当老和尚讲完第二遍后自动结束讲述,程序也就至此结束了。递归算法案例分析:
1、求解斐波那契数(Fibonacci number)
斐波那契数就是斐波那契数列中的数,斐波那契数的定义是:f(n)=f(n-1)+f(n-2),基本条件是f(n)=n (n<=1)
根据描述,可以定义函数:
def fibonacci(n):
if(n<=1) return n; // 定义结束条件,这时候不能再调用自己了
return fibonacci(n-1)+fibonacci(n-2); // 递归方程,调用自己
方法定义完毕,可以求解fibonacci(n),当n=1时,fibonacci(1)=1,递归带入,可以求出fibonacci(3)=2,fibonacci(10)=55
2、移动汉诺塔
汉诺塔是有三根柱子,假定是a,b,c,其中a柱子上有n个圆盘,下层的盘要比上一层的大,需要将这n个盘从a通过b柱子移动到c。
根据上面的需求, 对题解进行递归描述:
a、将a柱上的n-1个圆盘借助c柱移动到b柱上面
b、将第n个圆盘移动到c柱上面
c、将b柱上的n-1个圆盘借助a柱移动到c柱上面
所以定义功能如下:
def hanoi(n,a,b,c):
if(n==1) move(a,c);
else{
hanoi(n-1,a,c,b);
move(a,c);
hanoi(n-1,b,a,c);
}
def move( a,c):
System.out.println("move from "+ a+ " to "+c);
3、数据结构的递归定义
这类大部分是树的遍历及相关计算,树的先序、中序、后序遍历可以用以下函数定义:
a、先序遍历
def preOrder(Tree t):
print(t.value);
preOrder(t.left);
preOrder(t.right);
b、中序遍历
def preOrder(Tree t):
preOrder(t.left);
print(t.value);
preOrder(t.right);
c、后序遍历
def preOrder(Tree t):
preOrder(t.right);
preOrder(t.left);
print(t.value);
根据以上模板可以进行一些其他属性的计算,例如求解树的深度,树的深度可以描述为:
- 基本条件:如果树为null,直接返回0
- 遍历求解:
- 求解T.left 的深度 leftDep
- 求解T.right的深度 rightDep
- 如果leftDep>rightDep,返回leftDep+1,反之返回rightDep+1
所以求解树的深度可以定义为:
def TreeDep(Tree t):
if(t==null) return 0;
int leftDep=TreeDep(t.left);
int rightDep=TreeDep(t.right);
return leftDep>rightDep?leftDep+1:rightDep+1;
综上,满足递归调用的两个基本特征有:
a、寻找递归结束的基本条件
b、定义递归解的结构,也就是递归方程,最后将口头描述转换为代码结构