一:什么是递归?
若在一个函数(数据结构)里,直接或间接出现调用本身,则称它们为递归的;
二:什么时候使用递归?
(1) 数学定义是递归的
(2)数据结构是递归的
(3)问题的解法是递归的
这是什么意思呢?
(1) 数学定义是递归的
比如很多的数学定义都是递归定义,比如
1.阶乘
阶乘:Fact(n)
(1) 若n=0, 则返回1;
(2) 若n > 1, 则返回n*Fact(n-1);
例子:
long Fact(Long n){
if(n=0) return -1;
else return n * Fact(n-1);
}
- 二阶斐波拉契数列
斐波拉契数列:Fib(n)
(1) 若n=1或n=2, 则返回1;
(2) 若n > 2, 则返回Fib(n-1) + Fib(n-2);
例子:
long Fib(Long n){
if(n == 1 || n == 2) return 1;
else return Fib(n-1)+Fib(n-2);
}
对于类似这种的复杂问题,若能分解成几个简单且解法类似的子问题来求解,则称为递归求解;
3.分治法
什么时候使用分治法?
(1)能将一个大问题转变为一个小问题,而新问题和原问题解法类似或相同,不同的仅仅是处理的对象,并且这些处理更小且变化是有规律的;(可拆解)
(2)可以通过上述转化而使得问题简单化;(简化问题)
(3)必须有一个明确的递归出口(递归边界);(终止递归的条件)
void p(参数表,形参 ){
if(递归结束的条件) Return 结果; //递归边界
else p(参数); //递归的步棸
}
三:数据结构是递归的
其数据结构本身有递归的特性;
例如:对于链表,其节点LNode的定义有数据域data和指针域dext组成,而指针域next是一种指向LNode类型的指针,即LNode的定义中又用到了其自身,所以链表是一种递归的数据结构;
void TraverseList(LinkList p){
//递归的终止条件
if(p == NULL) return;
//递归步棸
else{
//输出当前节点的数据域
printf("%d",p->data);
//移动指针,输出下一个节点的数据域
TraverseList(p->next);
}
}
总结:在递归算法中,如果当递归结束条件成立,只执行Return操作时,分治法求解递归问题算法一般形式可以简化为:
void p(参数表,形参 ){
if(递归结束的条件) Return 结果; //递归边界
else p(参数); //递归的步棸
}
四:问题的解法是递归的?
有一类问题,虽然问题本身并没有明显的递归结果,但是采用递归求解比迭代求解更简单,例如:Hanoi塔问题,八皇问题,迷宫问题等;
五:递归过程与递归工作栈
一个递归函数,在函数的执行过程中,需要多次进行自我调用,那么思考一下,此时的递归函数是如何执行的?
在了解递归函数是如何执行之前,先了解一下任意两个函数之间的调用是如何进行的?
通常,当在一个函数的运行期间调用另一个函数时,在运行被调用函数之前,系统要做三件事:
1.将所有的实参,返回地址等信息调用传递给被调用函数保存;
2.为被调用函数的局部变量分配存储空间;
3.将控制权转移到被调用函数入口;
而从被调用函数返回到调用函数之前,系统同样要做三件事情:
1.保存被调用函数的计算结果;
2.释放被调用函数的数据区;
3.依照被调用函数保存的返回地址将控制权移动到调用函数;
当多个函数构成嵌套调用时,按照"先调用后返回"的原则,上述函数之间的信息传递和控制传递都必须通过"栈"来实现,即系统程序整个运行时的所需要的数据空间都安排在一个栈中,每当调用一个函数时,就在它的栈顶分配一个存储区,每当这个函数退出时,就释放它的存储区,则当前运行的函数的数据区必须在栈顶;
例如:
在主函数main中调用函数first函数,而在first函数中又嵌套调用了second函数,则当我们执行当前函数first时,则first函数的数据区在栈顶;而当我们执行second函数时,second函数的数据区在栈顶;
总结:
一个递归函数的运行过程类似多个函数的嵌套调用,只是调用函数和被调用函数都是同一个函数,因此,每次调用本身时,就会产生一个调用相关的一个重要概念就是递归函数运行的"层次".假设调用改递归函数的主函数为第0层,则从主函数调用递归函数进入到第一层,从第i层递归调用本函数进入下一层为第i+1层,反之退出第i层递归函数返回上一层为第i-1层;
为了保证递归函数正确执行,系统需要设立一个"递归工作栈"作为整个递归函数运行期间使用的数据存储区,每一层递归所需信息构成一个工作记录,其中包括所有实参,所有局部变量以及上一层的返回地址.每进入一层递归,就产生一个新的工作记录压入栈顶,每退出一个递归,就从栈顶弹出一个工作记录,则当前执行层的工作记录必须是递归工作栈栈顶的工作记录,此称为"活动记录";
