无聊 — 比较下线性递归和尾递归、函数调用和 lambda 演算
不多话，直接上图上真相…
代码：
-
#!/usr/local/bin/python2.6
-
#coding=utf-8
-
-
-
fib1 = lambda n: 1 if n < 3 else fib1(n – 2) + fib1(n – 1)
-
-
def fib2(n):
-
if n < 3:
-
return 1
-
return fib2(n – 2) + fib2(n – 1)
-
-
def fib3(n):
-
f = (lambda i, first, second:
-
second if i >= n else f(i + 1, second, first + second))
-
return f(1, 0, 1)
-
-
def fib4(n):
-
def _fib4(i, first, second):
-
if i >= n:
-
return second
-
return _fib4(i + 1, second, first + second)
-
return _fib4(1, 0, 1)
-
-
-
if __name__ == ‘__main__’:
-
for i in range(1, 41):
-
print fib1(i)
-
print fib2(i)
-
print fib3(i)
-
print fib4(i)
-
结论：
1. fib1/fib2 的 40 次调用累计 5 亿次以上的递归，总耗时 653 秒多；fib3 的 lambda 和 _fib4 的 40 次调用累计 820 次递归，总耗时不到 0.1 秒
2. 函数调用与 lambda 演算区别不大，5 亿次以上的递归调用，差异仍然保持在 20 秒内
3. 能用尾递的还用线递，都是虎逼青年…
Tail recursion is efficient because no stack frames are needed, it’s simply treated like a “for/while loop”, but it’s harder to read. Basically, you trade readability for performance, which is hard to take the decision.
Seth
20 Aug 09 at 8:46 pm
@seth
还好吧，我觉得可读性还是蛮高的，当然和线性递归比起来是差着一大截…
admin
21 Aug 09 at 2:24 am
你最近博瘾来了哇
hkbarton
21 Aug 09 at 9:51 am
楼上是虎逼青年，其实我是想写淘淘淘淘，华丽丽的桃…而且你说的博瘾怎么听怎么邪恶…
admin
21 Aug 09 at 5:17 pm