递归算法设计

递归是程序设计中一个很重要的课题。用递归技术设计的算法简单明了。递归算法的设计与分析是算法设计与分析的一大类。

首先，需要了解子程序调用的内部操作。其内部实现为两个方面。

1. 在执行调用时，系统至少需要执行以下操作：

1） 返回地址进栈，同时在栈顶为被调子程序的局部变量开辟空间；

2）为被调子程序准备数据：计算实参值，并赋给对应的栈顶的形参；

3）将指令流转入被调子程序的入口处。

2. 在执行返回操作时，系统至少需要执行的操作包括：

1）若有变参或者函数，将其值保存到回传变量中；

2）从栈顶取出返回地址；

3）按返回地址返回；

4）若有变参或者函数，从回传变量中取出保存的值传送给相应的变量或者位置上。

递归过程是自己调用自己的代码，一个递归过程的执行类似于多个子程序的嵌套调用。

使用递归会带来一些开销（栈空间，函数调用等），可以在算法设计的初期阶段使用递归，一旦所涉及的递归算法被证明为正确且确信是个好算法是，可以消去递归，把该算法翻译成等价的迭代过程，其效率通常要比原递归模型高，进一步简化这程序可使效率再次提高。

满足以下条件的问题可以考虑使用递归求解：

1）问题P的描述设计规模，即P(size)；

2）规模发生变化之后，问题的性质不发生变化；

3）问题的解决有出口。

其表现形式为：

递归伪算法

典型递归问题

【n阶汉诺塔】

【棋子移动】有2n个棋子(n>=4)排成一行，白子用0代表，黑子用1代表，n=5时的初始状态为

0 0 0 0 0 1 1 1 1 1 - - （右边至少有两个空位）

移动规则是：每次必须同时移动相邻两个棋子，颜色不限，移动方向不下；每次移动必须跳过若干棋子，不能调换两个棋子的位置。要求最后成为：

0 1 0 1 0 1 0 1 0 1

【求n个元素的全排列】

【自然数拆分】任何一个大于1的自然数，总可以拆分成若干个小于n的自然数之和，求所有的拆分。

递归算法的时间复杂度分析

根据递归算法的设计思路，可以建立算法时间复杂度的递归关系式，然后解方程求得算法的时间复杂度。

当递归关系式比较复杂时，若直接按递归关系实现算法，则算法的时间复杂度往往是非多项式时间，只是递归算法的一个不足。一种有效的解决办法是，利用数学解递归关系式，将结果或者中间过程编程实现，这样那个可以大大降低时间复杂度。

直接记住公式比较难，可以自己写递归关系式，然后试着解。比如：

n<=2, T(n)=C

n>2, T(n)=T(n-1)+T(n-2)

所以，T(n)<=2T(n-1)<=2^2T(n-2)<=...<=2^n-1T(1)=O(2^n)