做网站 广州,信息网官网,深圳国税局深圳做网站公司,app推广代理加盟文章目录1 递归的概念2 递归算法3 递归数据结构4 递归实现5 递归与循环差别1 递归的概念 递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己#xff0c;则称直接递归函数#xff1b;如果一个函数经过一系列的中间调用语句#xff0c;通过…
文章目录1 递归的概念2 递归算法3 递归数据结构4 递归实现5 递归与循环差别1 递归的概念 递归是指在定义自身的同时又出现了对自身的调用。如果一个函数在其定义体内直接调用自己则称直接递归函数如果一个函数经过一系列的中间调用语句通过其它函数间接调用自己则称间接递归函数。 说明递归定义的一个例子是斐波那契级数。它的定义可递归表示成:
2 递归算法
根据斐波那契级数的递归定义我们可以很自然地写出计算Fib的递归算法。为了便于在表达式中直接引用我们把它设计成一个函数过程用C语言描述如下
long Fiblong n
{ifn1return nelse return Fibn-2Fibn-1
}函数Fibn中又调用了函数Fibn-1和Fibn-2。这种在函数体内调用自己的做法称为递归调用。包含递归调用的函数称为递归函数。
递归模型不能循环定义必须满足以下三个条件 (1) 递归必须得有一个明确的终止条件 (2) 该函数所处理的问题规模必须在递减 (3) 这个转化必须是可解的。 递归的精髓在于能否将原始问题转化为属性相同但规模较小的问题
递归求解的思想 3 递归数据结构 数据结构原则上都可以采用递归的方法来定义但是习惯上许多数据结构并不采用递归方式而是直接定义如线性表、字符串和一维数组等。 其原因是这些数据结构直接定义更自然、更直截了当。 对于广义表和树通常给出的是它们的递归定义。使用递归方式定义的数据结构常称为递归数据结构。 4 递归实现
当多个函数嵌套调用时由于函数的运行规则是后调用先返回因此各函数占有的存储管理应实行“栈式管理”
当一个函数在运行期间调用另一个函数时在运行该被调用函数之前需先完成三件事 将所有的实在参数、返回地址等信息传递给被调用函数保存为被调用函数的局部变量分配存储区将控制转移到被调用函数的入口。 而从被调用函数返回调用函数之前应该完成 保存被调函数的计算结果释放被调函数的数据区依照被调函数保存的返回地址将控制转移到调用函数。 一个递归函数的运行过程类似于多个函数的嵌套调用差别仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进行操作在执行递归函数的过程中需要一个“递归工作栈”。 递归工作栈的作用是 将递归调用时的实在参数和函数返回地址传递给下一层执行的递归函数保存本层的参数和局部变量以便从下一层返回时重新使用它们。 递归算法优缺点分析 递归算法的优点是明显的程序结构简洁而清晰且易于分析因而许多高级语言都提供了递归机制。 但递归函数也有明显缺点它往往既费时又费空间。 如何将递归算法转换成非递归算法 通常借助栈来实现 比如二叉树的先中后序遍历递归与非递归实现非递归算法就是借助栈实现
5 递归与循环差别
递归循环易于理解不易理解速度慢速度快存储空间大存储空间小
分别用递归和循环的方式来求123……100的值。
采用递归
long sum( int n)
{ if( n 1) return 1; else return n sum( n – 1 ); } 采用循环
long sum(int n)
{long s0; int i; for(i0;in;i)si; return s;
}
