首页 ›存档› 技术 › 查看内容

递归算法转换为非递归算法的技巧

2018-3-30 13:00 |来自: 互联网 761 0

摘要: 来源：coderkian 链接：www.cnblogs.com/coderkian/p/3758068.html 递归函数具有很好的可读性和可维护性，但是大部分情况下程序效率不如非递归函数，所以在程序设计中一般喜欢先用递归解决问题，在保证方法正确的 ...

来源：coderkian

链接：www.cnblogs.com/coderkian/p/3758068.html

递归函数具有很好的可读性和可维护性，但是大部分情况下程序效率不如非递归函数，所以在程序设计中一般喜欢先用递归解决问题，在保证方法正确的前提下再转换为非递归函数以提高效率。

函数调用时，需要在栈中分配新的帧，将返回地址，调用参数和局部变量入栈。所以递归调用越深，占用的栈空间越多。如果层数过深，肯定会导致栈溢出，这也是消除递归的必要性之一。递归函数又可以分为尾递归和非尾递归函数，前者往往具有很好的优化效率，下面我们分别加以讨论。

尾递归函数

尾递归函数是指函数的最后一个动作是调用函数本身的递归函数，是递归的一种特殊情形。尾递归具有两个主要的特征：

调用自身函数(Self-called)；
计算仅占用常量栈空间(Stack Space)。

为什么尾递归可以做到常量栈空间，我们用著名的fibonacci数列作为例子来说明。

fibonacci数列实现方法一般是这样的，

intFibonacciRecur(intn){

if(0==n)return0;

if(1==n)return1;

returnFibonacciRecur(n-1) FibonacciRecur(n-2);

}

不过需要注意的是这种实现方法并不是尾递归，因为尾递归的最后一个动作必须是调用自身，这里最后的动作是加法运算，所以我们要修改一下，

intFibonacciTailRecur(intn,intacc1,intacc2){

if(0==n)returnacc1;

returnFibonacciTailRecur(n-1,acc2,acc1 acc2);

}

好了，现在符合尾递归的定义了，用gcc分别加-O和-O2选项编译，下面是部分汇编代码，

-O2汇编代码

FibonacciTailRecur:

.LFB12:

testl %edi,%edi

movl%esi,%eax

movl%edx,%esi

je.L4

.p2align4,,7

.L7:

leal(%rax,%rsi),%edx

decl%edi

movl%esi,%eax

testl %edi,%edi

movl%edx,%esi

声明：文章版权归原作者所有部分文章转自互联网如有侵权请联系 [邮箱地址] 删除

路过

雷人

握手

鲜花

鸡蛋

收藏分享邀请

上一篇：算法题 46：四叉树的叶节点（360笔试题）下一篇：在多伦多做生意必看！税收的各种算法你都懂了吗？

递归算法转换为非递归算法的技巧

相关分类