热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

经典的裴波拉契数列与尾递归实现

对于经典的裴波拉契数列:f(n)f(n-1)+f(n-2),f(0)0,f(1)1.(抱歉现在markdown里面插入latex公式还不会,后面再补咯)。

对于经典的裴波拉契数列:f(n) = f(n-1)+f(n-2), f(0) = 0, f(1) = 1.(抱歉现在markdown里面插入latex公式还不会,后面再补咯)。


  • 直接用递归实现,可以发现,当求f(n-1)时,需要从f(2)到f(n-2)的每一项值,求f(n-2)时需要f(2)到f(n-3)的每一项值,这中间包含了很多的重复,算法复杂度用树来分析,基本是一个满二叉树的节点数目,即O(2^n)。
    如何简化算法复杂度的问题,可以用长度为N的数组存储计算过的值,采用从2到N递推计算的方式,这种方法空间复杂度为O(N), 时间复杂度为O(N).采用求解系数矩阵,直接将[f(n) f(n-1)] 与[f(1) f(0)]联系起来,这样只要求矩阵方幂,并对N进行二进制分解,可将时间复杂度将至O(logN)。

  • 我们对递归方法进行一下优化,可以实现O(N)的时间复杂度,方法就是转化为尾递归:

int fibonacci(int n, int a, int b){
if(n == 0) return b;
else {
return fibonacci(n-1, b, a + b);
}
}

fibonacci(5, 0, 1);//example

这里实际上是将原来用两项f(n) 和 f(n-1)计算的结果放到了一个局部变量a+b中,并且由于该递归为尾递归,即递归部分是最后一步,可以实现原地递归:尾递归优化,不需要对先前的递归调用保留栈帧。这样就可以实现常数空间复杂度。

  • 尾递归来自于更加普通的尾调用:即对某函数的当前函数的最后一步,因此我们可以不用保存当前函数的局部变量,直接进入被调用的函数,因此实现尾调用优化,当函数在最后一步递归调用自身时,就是尾递归。

推荐阅读
author-avatar
白日做梦家_
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有