【递归过程】
指导
2021-08-08 09:58:22阅读人数:2837
什么是递归过程
递归过程指栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程,称做递归过程。递归是程序设计中一个强有力的工具。
递归过程的内容
一个直接调用自己或通过一系列的过程调用语句间接调用自己的过程,称作递归过程。
当一个过程的运行期间调用另一个过程时,在执行被调用过程之前,系统需先完成如下三件事:
1、将所有的实在参数,返回地址等信息传递给被调用的过程保存。
2、为被调用过程的局部变量分配存储空间。
3、将控制转移到被调用入口。
从被调过程返回调用过程
1、保存被调用过程的计算结果。
2、释放被调用过程的数据区。
3、依照被调过程保存的返回地址将控制转移到调用过程。
服从后调用先返回的原则。
基本原理是重复的把原问题转换为相似的新问题,直到把问题解决为止。
关键点:
1、用较简单的问题来表示较复杂的问题。
2、不能产生自己调用自己的无穷序列。即必须要有一个是递归出去的出口。。
递归的调用时通过栈来实现的。
“递归”过程是指调用自身的过程。通常,这不是编写VisualBasic代码的最有效方法。
其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数Fact(n)=1若n=1Fact(n)=n·Fact(n-1)若n>12阶Fibonacci数列Fib(n)=0若n=0Fib(n)=1若n=1Fib(n)=Fib(n-1)+Fib(n-2)其它情形和ackerman函数Ack(m,n)=n+1m=0Ack(m,n)=Ack(m-1,1)n=0Ack(m,n)=Ack(m-1,Ack(m,n-1))其它情形等;
其二,有的数据结构,如二叉树,广义表等,由于结构本身固有的递归特性,则它们的操作可递归地描述;
其三,还有一类问题,虽则问题本身没有明显的递归结构,用递归求解比迭代求解更简单,如八皇后问题,Hanio塔问题等。
请输入评论内容: