关于递归

递归是一个很有用的设计技术。在某些情况下，对于用其他方法很难解决的问题，使用递归就能给出一个自然、直接的简单解法。
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倍，这种差别还是很难分辨的。如果要比清晰性、易读性和代码的简洁性，那么这两个版本执行时间上的差别就可以忽略。递归解决方案通常比迭代简单，而且和源算法的逻辑一致性强。阶乘和幂运算就是这样的例子。