为什么fibonacci_tail()比fibonacci()快很多很多？

洛天依

'漫谈递归：从斐波那契开始了解尾递归 -- 简明现代魔法
'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, 下载次数: 48)

2014-11-13 20:52 上传

点击文件名下载附件

工作表中的内容仅为帮助自己理解弄的，不知注释的对么？
主要想请教如题，谢谢！

lee1892

第二个是伪递归，实际是迭代，当然快。

洛天依

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直接运算求出的，即每层都不曾发生过“完整的递归”。
怎样是完整的递归呢？在递归返回段，每次的调用都必须用到前一次的递归函数值。这样才算“完整的递归”,对吗？

coby001

fibonacci_tail

其实是用交换法

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

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

coby001

Function fibonacci(n)

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

洛天依

coby001 发表于 2014-11-13 22:58
fibonacci_tail

其实是用交换法

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

洛天依

coby001 发表于 2014-11-13 23:05
Function fibonacci(n)

这个是真递归了

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

coby001

也不算 伪递归 吧。

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

coby001

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

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

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

洛天依

尾递归和伪递归，可以划等号吗？
是不是真递归一定可以转换成尾递归呢？
现在，我觉着它俩好像都是披着递归的循环。