递归是一个很有用的设计技术。在某些情况下,对于用其他方法很难解决的问题,使用递归就能给出一个自然、直接的简单解法。
1、递归定义
递归定义由两部分组成。第一部分称作定位点或是基本例子,列出了构造集合中其他元素构造块的基本元素。第二部分,给出构造除基本元素之外的或是已经创建好的新对象的条件。这个条件可以再三地被用来生成新对象。
递归定义有两个目的:如前撰述的产生新元素,以及检查它是否是集合的一个元素。在检查时,先将一个问题简化。如果简化后仍然太复杂就继续简化,起到简化后的问题指向定位点。
2、方法调用和递归实现
方法调用时应当保存什么信息呢?道德是自动(局部)变量。如果一个包含局部变量x声明的方法f1()调用f2()方法,而f2()局部地声明了变量x,那么系统必须区分这两个变量x。如果f2()使用变量x,这表示它自己定义的x;如果f2()赋值给x,那么f1()的变量x的值不应被改变。当f2()结束后,f1()可以使用在f2()调用前赋值给x。当f1()和f2()相同时,就是一个方法对它自身的递归调用。那么系统是如何区分这两个变量x的呢?
第一种方法(包括main()方法)的状态都以所有自动变量的内容、方法的参数值以及表示调用程序重新开始处的返回地址为特征。包含所有这些信息的数据域定位在运行堆栈中,称为活动记录或是栈结构。只要其中的一个方法在执行,属于它的活动记录就存在。这个记录是该方法信息的一个私有池,一个存储正确执行及返回调用位置的必要信息的仓库。活动记录的生存周期通常很短,因为它们是在进入方法时动态分配并且在方法退出时动态回收的。只有main()的活动记录比其他活动记录的生存周期长些。
一个活动记录通常包含以下信息:
该方法所有的参数值,首单元地址(如果传递的是数组或是引用变量的话),所有其他数据项的拷贝。
可以存在别处的局部变量,活动记录只包含它们的描述符和指向它们存储地址的指针。
存储一个返回地址将控制权给调用程序,这个地址是紧跟在调用指令后的第一条指令的地址。
一个动态连接,即一个指向调用程序活动记录的指针。
一个未被声明为void类型的方法的返回值。因为每个调用的活动记录的大小都是不同的,所以返回值就放在调用程序的活动记录的前面。
如前撰述,如果一个方法被main()或另一个方法调用,那么它的活动记录就创建在运行堆栈中。运行堆栈总是反映方法的当前状态。例如,假设main()调用方法f1(),f1()调用f2(),而f2()又调用f3()。如果f3()正在执行中,那么运行堆栈的状态如图所示。根据堆栈的性质,如果弹出了f3()的活动记录,只要将指针移到f3()的返回值下面就可以,那么f2()又恢复运行,并可以自由地访问重新被激活运行所必需的信息私有池。另一方面,如果f3()刚巧又调用了另一个该方法f4(),那么运行堆栈将上移栈顶指针,因为f4()的活动记录被创建在堆栈中并且f3()会被挂起。
无论何时调用一个方法都会创建一个活动记录,这使得系统可以正确处理递归。递归是调用一个和调用者同名的方法,所以一个递归调用并不是一个方法调用其自身,而是方法的一个实例调用相同方法的另一个实例。在计算机内部,这些调用是用不同的活动记录表示并由系统区分的。
小结:
递归通常比它的迭代形式效率低。但是打个比方,如果一个递归程序执行100ms,而它的迭代公需要10ms,那么尽管后者比前者快10倍,这种差别还是很难分辨的。如果要比清晰性、易读性和代码的简洁性,那么这两个版本执行时间上的差别就可以忽略。递归解决方案通常比迭代简单,而且和源算法的逻辑一致性强。阶乘和幂运算就是这样的例子。
分享到:
相关推荐
关于递归算法时间复杂度分析的探讨.pdf
python基础(补充):关于递归的优化(使用缓存)
关于递归教学的探讨.zip
关于递归教学的探讨.doc
关于递归神经网络的一个结果.pdf
一个算法的实现,关于在递归时间复杂度上的考证
x=fib(n-1)+fib(n-2);
关于递归
关于递归的教程,教你如何学好递归,掌握递归,
Avalon读取xml 没写成通用的 但是我用递归的算法 还是将xml中的内容赋值给了 我写的特定的javabean
c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘 n!c++ 递归 阶乘...
一个不错的关于递归的综合讲解教材,涉及覆盖面积广,涵盖了要运用递归思想的所有东西。总之,帮我们梳理关于递归的所有东西。很好的材料,用数学的思想讲解分析递归,理论性强。
宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归宏递归
C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归C#递归
c++实现的关于递归实现逆序字符串,有需要的可以下载
一个关于递归下降语法分析器设计的文档
关于递归知识点,让初学者可以更详细地了解递归的使用方法
信息科学技术学院《程序设计实习》关于递归的基本思想
java中关于递归的相关知识点和具体的实例,是一片不错的值得学习的详细资料
JAVA编程(递归典型题目)关于递归的~