# 最爱fibonacci

Fibonacci 的算法如下：

```%% regular recursive fibonacci
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).```

上面的实现问题在于时间复杂度：O(2^N)，单单这个数字有点抽象，试试运算fib(50)，看看要多久（本人没有足够的耐心等了），这个小的数字50都要花费那么长的时间，那fib(10000)呢？

下面函数语言FP的尾递归(tail recursion)就要上场了.

```%% tail recursive fibonacci
fib2_tr(0, Result, _Next) -> Result;
fib2_tr(Iter, Result, Next) when Iter > 0 -> fib2_tr(Iter-1, Next, Result+Next).
fib2(N) -> fib2_tr(N, 0, 1).```

上面的程序时间复杂度为 O(N)，算一下fib2(10000)，立马出结果：

```[root@localhost ~]# cat fibonacci.erl
#!/usr/local/bin/escript

%% regular recursive fibonacci
fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

%% tail recursive fibonacci
fib2_tr(0, Result, _Next) -> Result;
fib2_tr(Iter, Result, Next) when Iter > 0 -> fib2_tr(Iter-1, Next, Result+Next).
fib2(N) -> fib2_tr(N, 0, 1).

main(Arg) ->
io:format("~p~n", [fib2(10000)]).

[root@localhost ~]# time escript fibonacci.erl
fibonacci.erl:5: Warning: function fib/1 is unused
fibonacci.erl:16: Warning: variable 'Arg' is unused
33644764876431783266621612005107543310302148460680063906564769974680081442166662368155595513633734025582065332680836159373734790483865268263040892463056431887354544369559827491606602099884183933864652731300088830269235673613135117579297437854413752130520504347701602264758318906527890855154366159582987279682987510631200575428783453215515103870818298969791613127856265033195487140214287532698187962046936097879900350962302291026368131493195275630227837628441540360584402572114334961180023091208287046088923962328835461505776583271252546093591128203925285393434620904245248929403901706233888991085841065183173360437470737908552631764325733993712871937587746897479926305837065742830161637408969178426378624212835258112820516370298089332099905707920064367426202389783111470054074998459250360633560933883831923386783056136435351892133279732908133732642652633989763922723407882928177953580570993691049175470808931841056146322338217465637321248226383092103297701648054726243842374862411453093812206564914032751086643394517512161526545361333111314042436854805106765843493523836959653428071768775328348234345557366719731392746273629108210679280784718035329131176778924659089938635459327894523777674406192240337638674004021330343297496902028328145933418826817683893072003634795623117103101291953169794607632737589253530772552375943788434504067715555779056450443016640119462580972216729758615026968443146952034614932291105970676243268515992834709891284706740862008587135016260312071903172086094081298321581077282076353186624611278245537208532365305775956430072517744315051539600905168603220349163222640885248852433158051534849622434848299380905070483482449327453732624567755879089187190803662058009594743150052402532709746995318770724376825907419939632265984147498193609285223945039707165443156421328157688908058783183404917434556270520223564846495196112460268313970975069382648706613264507665074611512677522748621598642530711298441182622661057163515069260029861704945425047491378115154139941550671256271197133252763631939606902895650288268608362241082050562430701794976171121233066073310059947366875

real    0m0.472s
user    0m0.342s
sys     0m0.114s```

相比之下，用第一种算法计算fib(10000)估计要等到天荒地老了。

fibonacci的尾递归算法与普通递归算法的实质区别在于：尾递归是自底向上计算，而普通递归则是自顶向下计算，普通递归计算中包含了大量的重复运算。

这里告诉我们tail recursion在FP中不仅仅是对stack grow的优化，更是一种算法思维的升华。

在SICP一书中fib和fac讲的很透彻，不过SICP里讲的是scheme lisp，点这里

lisp版的fib应该是这样：

```(define (fib n)
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
(fib-iter 1 0 n))```

lisp版的fac应该是这样：

```(define (factorial n)
(define (iter product counter)
(if (> counter n)
product
(iter (* counter product)
(+ counter 1))))
(iter 1 1))```

```Prelude> let fib = 1:1:(zipWith (+) fib \$ tail fib) in fib
[1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711```

一行搞定，有人问用同是FP的Erlang或scheme可以写的这样精炼吗？我不知道，起码Erlang和scheme都不是lazy的。

```Prelude> let sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p > 0] in sieve [2..]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109```

```Prelude> let fac n = product [1..n] in fac 50
30414093201713378043612608166064768844377641568960512000000000000```

• 0

开心

• 0

板砖

• 0

感动

• 0

有用

• 0

疑问

• 0

难过

• 0

无聊

• 0

震惊

1．最爱你的女人,会在你晚上睡觉打呼噜的时候,轻轻吻吻你而不吵醒你,因为她知道你累了. 2．最爱你的
Another kind of Fibonacci Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K

One thing you need to keep in mind about finding the time complexity of a recursive function