浅谈递归机制和非递归转换

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

首先，什么是递归

许多数据结构是根据递归性质定义的，因为这些结构的固有性质。递归是指函数直接或间接调用自身。问题的求解过程被分成许多性质相同的子问题，小问题的求解过程很容易找到，这些子问题的解构成原问题的解。

二、递归的几个特征

1.递归，即如何把原问题分成子问题。

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

3.有界函数，问题规模变化的函数，保证递归的规模接近导出条件。

3.递归操作机制

很明显，很多问题的内在本质决定了这类问题是递归定义，所以递归的程序是直截了当的，结构清晰，思路清晰。但是递归的执行过程令人费解，这也是很多人觉得递归难以理解的原因之一。因为递归调用是对函数本身的调用，所以在一个调用结束之前会开始另一个调用。根据作用域的规定，函数被占用的空空间在执行终止前是无法回收的，必须保存，也就是说每次调用都必须保存相应的空分配的空间。为了更好的管理这些空房间，系统内部设置了一个堆栈，用来存储每次函数调用和返回所需的各种数据，包括函数调用结束的返回地址、返回值、参数和局部变量。

流程大致如下:

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

2.分配空房间，堆栈第一个地址，保护现场。

3.转到函数体并执行每条语句。将重复前面的部分(递归调用)

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

第四，引入非递归。

从用户的角度来看，递归真的很简单，很容易从宏观上理解程序。虽然递归程序的时间复杂度可以根据T(n)=T(n-1)*f(n)递归计算，其中f(n)为递归执行时间复杂度，但一般来说，时间复杂度与对应的非递归相似，但递归的效率相当低。主要是花钱在反复推入推出的机制和各种中断上(详见操作系统)。

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

1.一般来说，根据是否需要回朔，递归可以分为简单递归和复杂递归。简单递归一般是根据递归公式找出递归公式(这就引出了分治思想和动态规划)。复杂递归一般是模拟系统处理递归的机制，通过将栈或队列等数据结构保存回新月点来解决。