考试大编辑推荐：计算机二级C语言辅导知识

　　一、什么是递归

　　很多数据结构的定义都是根据递归性质来进行定义的，是因为这些结构固有的性质。递归是指某个函数直接或间接的调用自身。问题的求解过程就是划分成许多相同性质的子问题的求解，而小问题的求解过程可以很容易的求出，这些子问题的解就构成里原问题的解了。

　　二、递归的几个特点

　　1.递归式，就是如何将原问题划分成子问题。

　　2.递归出口，递归终止的条件，即最小子问题的求解，可以允许多个出口。

　　3.界函数，问题规模变化的函数，它保证递归的规模向出口条件靠拢

　　三、递归的运做机制

　　很明显，很多问题本身固有的性质就决定此类问题是递归定义，所以递归程序很直接算法程序结构清晰、思路明了。但是递归的执行过程却很让人费解，这也是让很多人难理解递归的原因之一。由于递归调用是对函数自身的调用，在一次调用没有结束之前又开始了另外一次调用，按照作用域的规定，函数在执行终止之前是不能收回所占用的空间，必须保存下来，这也就意味着每一次的调用都要把分配的相应空间保存起来。为了更好管理这些空间，系统内部设置一个栈，用于存放每次函数调用与返回所需的各种数据，其中主要包括函数的调用结束的返回地址，返回值，参数和局部变量等。

　　其过程大致如下：

　　1.计算当前函数的实参的值

　　2.分配空间，并将首地址压栈，保护现场

　　3.转到函数体，执行各语句，此前部分会重复发生（递归调用）

　　4.直到出口，从栈顶取出相应数据，包括，返回地址，返回值等等，收回空间，恢复现场，转到上一层的调用位置继续执行本次调用未完成的语句。

　　四、引入非递归

　　从用户使用角度来说，递归真的很简便，对程序宏观上容易理解。递归程序的时间复杂度虽然可以根据T（n）=T（n-1）*f（n）递归求出，其中f（n）是递归式的执行时间复杂度，一般来说，时间复杂度和对应的非递归差不多，但是递归的效率是相当低的它主要发费在反复的进栈出栈，各种中断等机制上（具体的可以参考操作系统）更有甚者，在递归求解过程中，某些解会重复的求好几次，这是不能容忍的，这些也是引入非递归机制的原因之一。

　　五、递归转非递归的两种方法

　　1.一般根据是否需要回朔可以把递归分成简单递归和复杂递归，简单递归一般就是根据递归式来找出递推公式（这也就引申出分治思想和动态规划）。而复杂递归一般就是模拟系统处理递归的机制，使用栈或队列等数据结构保存回朔点来求解。