python 实现斐波那契数列

[zangxixi]

各位 pythoner 们，大家来分享用 python 实现斐波那契数列的不同做法吧！！~\(≧▽≦)/~

[mikej]

@florije return 完了没输出。。

[mouer]

fib = lambda n : 1 if n <= 2 else fib(n - 1) + fib(n - 2)

[florije]

@mikej 不好意思，格式都被吃了……写 python 的应该能看出来缩进吧……

[tempuseraccount]

由此工作中还真有用了 fibonacci 数列的地方。
真使用的话还是最好把值存在数组里直接取。能少算尽量少算

[wentian]

def fib():
fib1,fib2 = 1, 1
while True:
yield fib1
fib1, fib2 = fib2, fib1+fib2

[mikej]

@florije 怎样缩进这里都只输出了一个数嘛。。

[dofy]

可以贴 gist

[ipconfiger]

print [x[0] for x in [ (a[i][0], a.append((a[i][1], a[i][0]+a[i][1]))) for a in ([[1,1]], ) for i in xrange(100) ]]

一行

[RqPS6rhmP3Nyn3Tm]

Python 官网就有，一行搞定

[RqPS6rhmP3Nyn3Tm]

来个神经病版的

print '1,1,2,5,7,12,19,31,50'

[wellsc]

```
def fib(n):
f1 = f2 = 1
for k in range(1, n)
f1, f2 = f2, f2 + f1
return f2
```

[bdbai]

@random2case 俺不懂 fp ，不过用递归的效率真的好吗？

[mailto1587]

递归不 memoize 一下？

```
memo = {1: 1, 2: 1}
fib = lambda n: memo.get(n) or memo.setdefault(n, fib(n - 1) + fib(n - 2))
```

这方案的缺陷是，需要慢慢调教它，一下子 fib(5000)肯定会撒娇，需要 fib(1000)、 fib(2000)、 fib(3000)、 fib(4000)、 fib(5000)， Done ！

[random2case]

@bdbai 尾递归好的多，如 @fulvaz 所说的，加上了缓存，效率也高多了，据说相当于循环。尾递归不会每一次都分配新栈了。但是看着难理解了，幸好 scala 有一个 @tailrec 检查是否是尾递归呢。
def fib_out(n:Int):Int={
@tailrec
def _loop(n:Int,acc1:Int,acc2:Int):Int={
if(n < 2) acc2 else _loop(n-1,acc2,acc1+acc2)
}
_loop(n,1,1)
}
函数式编程是程序员的一个福利吧，如果你喜欢，并且可以因此发挥你的才智，创造，获得快乐。那么你完全可以享用它，同时，函数式编程作为一个福利，你也可以选择拒绝它。

[random2case]

@mailto1587 把俺写的这个 Int 换成 BigInt,试了下， fib(5000)瞬间出来了， 6276302800488957086035253108349684055478528702736457439025824448927937256811663264475883711527806250329984690249846819800648580083040107584710332687596562185073640422286799239932615797105974710857095487342820351307477141875012176874307156016229965832589137779724973854362777629878229505500260477136108363709090010421536915488632339240756987974122598603591920306874926755600361865354330444681915154695741851960071089944015319300128574107662757054790648152751366475529121877212785489665101733755898580317984402963873738187000120737824193162011399200547424034440836239726275765901190914513013217132050988064832024783370583789324109052449717186857327239783000020791777804503930439875068662687670678802914269784817022567088069496231111407908953313902398529655056082228598715882365779469902465675715699187225655878240668599547496218159297881601061923195562143932693324644219266564617042934227893371179832389642895285401263875342640468017378925921483580111278055044254198382265567395946431803304304326865077742925818757370691726168228648841319231470626 ，俺没办法把 fib(100000)贴上来，这装不下。但是也是不到一秒。

[happywowwow]

@BXIA
你这数列有点奇怪...
1,1,2,3,5,8,13

[kevinyoung]

@songkaiape 第一次会把奇数编号的去掉，剩下偶数编号的全部编号除以二，再进行这个过程，所以最后剩下的那个肯定是 100 以内最“偶”的那个， 64

[shyling]

@random2case 要有尾递归优化的尾递归才有用吧=。=， py 嘛~~~~~

[kevinyoung]

@bdbai 我觉得递归最大的好处是有些问题用递归的语言描述非常简洁，比如快排比如对树进行操作，但这并不总是成立的

回到 python ， python 虽然能递归，但并不会自动做尾递归优化，所以递归算这种东西可能会爆栈，另外函数调用也会造成额外的时间开销，直观的看同样作用的 python 代码，循环的就是比递归的快。所以写 python 的话其实不推荐写递归，而是想办法写成循环好一些

其他的语言另说，比如 Haskell 根本没有循环只能写递归，或者有些语言递归优化的好也可以。

[random2case]

@shyling python 尾递归是否优化，俺不太清楚，俺只是拿 python 做一些简单的事，对语言本身不了解。但是 scala 确实是对尾递归做过优化的。 https://www.google.com/#q=+scala+tail+recursion ，自行 google 一下吧。

如 @kevinyoung 所说， Haskell 根本没有循环只能写递归。 scala 借鉴了 Haskell 。但是 scala 也可以写循环的。