《递归算法和非递归算法的区别和转换》由会员分享,可在线阅读,更多相关《递归算法和非递归算法的区别和转换(2页珍藏版)》请在金锄头文库上搜索。
1、递归算法和非递归算法的 difference 和转换递归算法实际上是一种分而治之的方法,它把复杂问题分解为简单问题来求解。对于某些复杂问题(例如 hanio 塔问题) ,递归算法是一种自然且合乎逻辑的解决问题的方式,但是递归算法的执行效率通常比较差。因此,在求解某些问题时,常采用递归算法来分析问题,用非递归算法来求解问题;另外,有些程序设计语言不支持递归,这就需要把递归算法转换为非递归算法。将递归算法转换为非递归算法有两种方法,一种是直接求值,不需要回溯;另一种是不能直接求值,需要回溯。前者使用一些变量保存中间结果,称为直接转换法;后者使用栈保存中间结果,称为间接转换法,下面分别讨论这两种方法
2、。1. 直接转换法直接转换法通常用来消除尾递归和单向递归,将递归结构用循环结构来替代。尾递归是指在递归算法中,递归调用语句只有一个,而且是处在算法的最后。例如求阶乘的递归算法:long fact(int n)if (n=0) return 1;else return n*fact(n-1);当递归调用返回时,是返回到上一层递归调用的下一条语句,而这个返回位置正好是算法的结束处,所以,不必利用栈来保存返回信息。对于尾递归形式的递归算法,可以利用循环结构来替代。例如求阶乘的递归算法可以写成如下循环结构的非递归算法:long fact(int n)int s=0;for (int i=1; is=s
3、*i; /用 s 保存中间结果return s;单向递归是指递归算法中虽然有多处递归调用语句,但各递归调用语句的参数之间没有关系,并且这些递归调用语句都处在递归算法的最后。显然,尾递归是单向递归的特例。例如求斐波那契数列的递归算法如下:int f(int n)if (n= =1 | | n= =0) return 1; else return f(n-1)+f(n-2);对于单向递归,可以设置一些变量保存中间结构,将递归结构用循环结构来替代。例如求斐波那契数列的算法中用 s1和 s2保存中间的计算结果,非递归函数如下:int f(int n)int i, s;int s1=1, s2=1;for (i=3; i=n; +i)s=s1+s2;s2=s1; / 保存 f(n-2)的值s1=s; /保存 f(n-1)的值return s;2. 间接转换法该方法使用栈保存中间结果,一般需根据递归函数在执行过程中栈的变化得到。其一般过程如下:将初始状态 s0进栈while (栈不为空)退栈,将栈顶元素赋给 s;if (s 是要找的结果) 返回 ;else 寻找到 s 的相关状态 s1;将 s1进栈间接转换法在数据结构中有较多实例,如二叉树遍历算法的非递归实现、图的深度优先遍历算法的非递归实现等等。