问题

费波那契数列（意大利语：Successione di Fibonacci），又译费波拿契数、斐波那契数列、斐波那契数列、黄金分割数列。

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

  1. F0 = 0     (n=0)
  2. F1 = 1    (n=1)
  3. Fn = F[n-1]+ F[n-2](n=>2)

关于Fibonacci的精彩解释，请看下列视频：

TED-神奇的斐波那契数列

如果要查看文字解释，请看维基百科词条：斐波那契数列

思路说明

几乎所有的高级语言都要拿Fibonacci数列为例子，解释递归、循环等概念。这里，我要用Python来演示一下，各种不同的写法，供参考。

解决（python）

递归——按照定义直接写

这种方法不是一个好方法，因为它的开销太大，比如计算fib1(100),就需要耐心等待较长一段时间了。所以，这是一种不实用的方法。但是，因为简单，列为第一种。

  1. def fib1(n):
  2.     if n==0:
  3.         return 0
  4.     elif n==1:
  5.         return 1
  6.     else:
  7.         return fib1(n-1) + fib1(n-2)

递归，进行初始化

fib1的慢，就是因为每次都要计算前面已经算过的项目.这里将上述算法进行稍微改进。速度快了很多。

  1. memo = {0:0, 1:1}
  2. def fib2(n):
  3.     if not n in memo:
  4.         memo[n] = fib2(n-1)+fib2(n-2)
  5.     return memo[n]

迭代

  1. def fib3(n):
  2.     a, b = 0, 1
  3.     for i in range(n):
  4.         a, b = b, a+b
  5.     return a

直接理论数学结论

在维基百科的词条 里面，已经列出了不同形式的Fibonacci数列的数学结果，可以直接将这些结果拿过来，通过程序计算，得到斐波那契数。此类程序，本文略。

这种方法来自网络

  1. print('!* Fibonacci Sequence python \n')
  2. def Fibonacci_Series():
  3.     x = input('Enter Series length to print fibonacci sequence')
  5.     d,e=0,1
  6.     a = []
  7.     a.append(d)
  8.     a.append(e)
  9.     while(x!=2):
  10.         c = d + e
  11.         d = e
  12.         e = c
  13.         a.append(c)
  14.         x = x -1
  15.     print(a)