斐波那契数列

2009-08-09 09:59:56 来自: Fleurer(白天不懂夜的黑)

初学递归的时候都喜欢拿它做例子，不过重复计算太多，未接触过fp的同学认为“递归效率低”，我相信很大程度上来自这个例子的泛滥。

“效率”高低只跟复杂度有关，尾递归优化并不会影响到程序的复杂度。所以需要memo来消去重复计算。haskell搞这个还是很漂亮的～

import Data.Array

fib n = fib' n
__where
____memo = array (0,n) [(i,fib' i)| i<- [0..n]]
____fib' 1 = 1
____fib' 2 = 1
____fib' x = memo!(x-1) + memo!(x-2)

2009-08-10 20:55:25 ngU khO

I don't think tail recursion is by any means useful in such lazy languages as Haskell...

> 删除
2009-08-10 21:35:38 Fleurer (白天不懂夜的黑)

楼上能详细讲讲么...不解呢...

> 删除
2009-08-19 15:22:55 Jnny

难道说的是HASKELL里本来就是lazy language 自己实现了记忆重复计算的值不用自己专门用一个memo去存。。。

> 删除
2009-08-19 16:54:08 Fleurer (白天不懂夜的黑)

@jnny
用memo自动记忆重复计算应该是程序员的事情吧。上面那个斐波那契数列的程序里就有个做memo的数组

> 删除