Python和ELM榆木语言实现基本算法2:斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。

在数学上，斐波那契数列是以递归的方法来定义：

• {\displaystyle F_{0}=0}
• {\displaystyle F_{1}=1}
• {\displaystyle F_{n}=F_{n-1}+F_{n-2}}（n≧2）

用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……

一、python用递归实现代码：

def fibonacci(m):
    if m <= 2:
       return 1
    else:
       return fibonacci(m-1) + fibonacci(m-2)
for i in range(1000):    print(fibonacci(i))

二、ELM榆木用递归实现代码：

import Html exposing (text,div)
import Debug exposing (toString)
import List exposing (range,map)

fibonacci : Int -> Int
fibonacci n =    
      case n of
            0 ->
               1
            1 ->
               1
            2 ->
               1       
            _ -> 
               fibonacci (n-2) + fibonacci (n-1)
view m =  text <| (++) " " <| Debug.toString <| fibonacci m
main =  div []    (List.map (\x -> view x) <| range 1 20) 

三、python用数组记忆化搜索代码：

当m很大时，递归的运行速度会明显变慢。根本原因在于递归算法进行了大量的重复运算。所以可以开一个数组，记录每个被计算过的函数值。每次调用函数时，如果函数被计算过，就直接调用计算好的结果。

temp = [0]*10000
def fibonacci(m):    
       if temp[m] != 0:             #实现记忆化搜索优化
             return temp[m]    
       else:        
             if m <= 2:
                    return 1
             else:
                     return fibonacci(m-1) + fibonacci(m-2)

for i in range(1000):
       print(fibonacci(i))

四、虽然记忆搜索优化后快了很多，但仍然不是最好的。本问题递推顺序明显，用一个for循环就可以解决问题了。

python 代码如下：

m1 = 1
m2 = 1
m3 = 1
print(m1)
print(m2)
for i in range(3,10,1):
    m3 = m1 + m2
    m1 = m2
    m2 = m3
    print(m3)

本节总结：递归很适合表示斐波那契数列，但for循环更快，据说elm榆木语言的尾递归实现也和for循环有类似的性能，有时间尝试实现。