计算机二级考试C语言辅导：浅谈递归机制和非递归转换

一、什么是递归
很多数据结构都是根据递归性质来定义的，因为这些结构的固有性质。递归是指函数直接或间接调用自身。问题的求解过程被分成许多性质相同的子问题，小问题的求解过程很容易找到，这些子问题的解构成原问题的解。
二、递归的几个特征
1。递归就是如何把原问题分成子问题。
2。递归退出，递归终止的条件，即最小子问题的解，可以允许多重退出。
3。有界函数，问题尺度变化的函数，保证递归的尺度接近导出条件
3。递归的运算机制
显然，很多问题的固有性质决定了这类问题是递归定义，所以递归程序非常直接。算法程序结构清晰，思路清晰。但是递归的执行过程令人费解，这也是很多人觉得递归难以理解的原因之一。因为递归调用是对函数本身的调用，所以在一个调用结束之前会开始另一个调用。根据作用域的规定，函数被占用的空空间在执行终止前是无法回收的，必须保存，也就是说每次调用都必须保存相应的空分配的空间。为了更好的管理这些空房间，系统内部设置了一个堆栈，用来存储每次函数调用和返回所需的各种数据，包括函数调用结束的返回地址、返回值、参数和局部变量。
过程大致如下:
1。计算当前函数的参数值
2。分配空并堆栈首地址保护场景
3。转到函数体，执行每条语句，前面的部分会重复(递归调用)[
IV。介绍非递归
从用户的角度来看，递归真的很简单，很容易从宏观上理解程序。虽然递归程序的时间复杂度可以根据T(n)=T(n-1)*f(n)递归计算，其中f(n)为递归执行时间复杂度，但一般来说，时间复杂度与对应的非递归相似，但递归的效率相当低。主要是花钱在反复推入推出的机制和各种中断上(详见操作系统)。
五、递归到非递归的两种方法
1。一般递归根据是否需要回朔，可以分为简单递归和复杂递归。简单递归一般是根据递归公式求递归公式(这就引出了分而治之和动态规划的思想)。复杂递归一般是模拟系统处理递归的机制，通过将栈或队列等数据结构保存回新月点来解决。