ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

EH搜索     
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 EH云课堂直播课程免费学 打造核心竞争力的职场宝典
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
查看: 2197|回复: 17

[求助] 为什么fibonacci_tail()比fibonacci()快很多很多?

[复制链接]

TA的精华主题

TA的得分主题

发表于 2014-11-13 20:54 | 显示全部楼层 |阅读模式
本帖已被收录到知识树中,索引项:递归
'漫谈递归:从斐波那契开始了解尾递归 -- 简明现代魔法
'http://www.nowamagic.net/librarys/veda/detail/2325
Sub main()
    Dim t, n
    n = 34
    t = Timer: Debug.Print fibonacci(n), Timer - t & "s"
    t = Timer: Debug.Print fibonacci_tail(n, 1, 1), Timer - t & "s"
End Sub
'
Function fibonacci(n)
    If n <= 2 Then
        fibonacci = 1
    Else
        fibonacci = fibonacci(n - 1) + fibonacci(n - 2)
    End If
End Function
'
Function fibonacci_tail(n, acc1, acc2)
    If n < 2 Then
        fibonacci_tail = acc1
    Else
        Debug.Print n - 1, acc2, acc1 + acc2
        fibonacci_tail = fibonacci_tail(n - 1, acc2, acc1 + acc2)
    End If
End Function
dg.rar (29.74 KB, 下载次数: 36)

TA的精华主题

TA的得分主题

发表于 2014-11-13 22:09 来自手机 | 显示全部楼层
第二个是伪递归,实际是迭代,当然快。

评分

参与人数 1鲜花 +1 收起 理由
洛天依 + 1 感谢帮助

查看全部评分

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-11-13 22:49 | 显示全部楼层
lee1892 发表于 2014-11-13 22:09
第二个是伪递归,实际是迭代,当然快。

形参时
n .............. 数列的第n个值
acc1 ........... 数列的第1个值
acc2 ........... 数列的第2个值
调用时
n-1 ............ 下一层的形参1
acc2 ........... 下一层的形参2
acc1+acc2 ...... 下一层的形参3


谢谢lee1892!
除非想不出怎么循环,而问题比较适合递归,我才接触递归。所以,递归题我很不熟。每次都得先回想一下最基本的原理。经你解释后,我这样理解对吗?
这里,在fibonacci_tail()的递归返回段,每层的递归函数值都是由形参2和形参3直接运算求出的,即每层都不曾发生过“完整的递归”。
怎样是完整的递归呢?在递归返回段,每次的调用都必须用到前一次的递归函数值。这样才算“完整的递归”,对吗?

TA的精华主题

TA的得分主题

发表于 2014-11-13 22:58 | 显示全部楼层
fibonacci_tail

其实是用交换法

a=1
b=1
for i=3 to n
   tmp=a+b
   a=b
   b=tmp
next

一直滚动跌代向前,直到算出Fib(n)

评分

参与人数 1鲜花 +1 收起 理由
洛天依 + 1 感谢帮助

查看全部评分

TA的精华主题

TA的得分主题

发表于 2014-11-13 23:05 | 显示全部楼层
Function fibonacci(n)

这个是真递归了
要用到 内存栈 来临时保存函数调用的“现场” ,函数返回后,又恢复现场,
很罗嗦,速度慢,n太大时会溢出。

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-11-13 23:22 来自手机 | 显示全部楼层
coby001 发表于 2014-11-13 22:58
fibonacci_tail

其实是用交换法

谢谢coby001!
原来这题的等效循环是这样的哦,确实好理解点。
1楼链接的作者称作尾递归;而lee1892和你都称作伪递归。我不大相信是作者笔误,这两种称呼都对吗?或是有什么原因吗

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-11-13 23:35 来自手机 | 显示全部楼层
coby001 发表于 2014-11-13 23:05
Function fibonacci(n)

这个是真递归了

对于fibonacci(),在单位电脑测试时,n最大可以是3311,如果n=3312,就溢出。你说的“现场”,让我有想到:一个现场中有一个形参n,形参是在栈内存中开辟空间的,当出现了足够多的形参后,栈内存装不下,所以才报溢出。不知道对不对?

TA的精华主题

TA的得分主题

发表于 2014-11-13 23:36 | 显示全部楼层
也不算 伪递归 吧。

fibonacci_tail = fibonacci_tail(n - 1, acc2, acc1 + acc2)
当这句发生递归时,函数中的参数都是已经计算好了的,不用另外计算,也就不用保存现场,编译器会优化此调用过程,重复使用原来的栈。
速度比真递归快,也不溢出,
但毕竟发生了函数调用,所以,比 直接循环 慢些。

TA的精华主题

TA的得分主题

发表于 2014-11-13 23:53 | 显示全部楼层
洛天依 发表于 2014-11-13 23:35
对于fibonacci(),在单位电脑测试时,n最大可以是3311,如果n=3312,就溢出。你说的“现场”,让我有想到 ...

很好理解的。
就像你正在做某件事,做到一半,没做完,突然电话响了,你要去接电话,就用一个本子记住事情做到哪里了。
接完电话回来,你看看本子,就恢复原来的工作状态继续做事。

如果有太多的事没做完,需要记住,而本子的页面是有限的,写不下那么多,就溢出了~

TA的精华主题

TA的得分主题

 楼主| 发表于 2014-11-14 00:05 来自手机 | 显示全部楼层
尾递归和伪递归,可以划等号吗?
是不是真递归一定可以转换成尾递归呢?
现在,我觉着它俩好像都是披着递归的循环。
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,高效办公专列,每天发车

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2019-10-22 03:57 , Processed in 0.111356 second(s), 20 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2020 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表