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