用Python实现斐波那契（Fibonacci）函数
Fibonacci斐波那契数列，很简单，就是一个递归嘛，学任何编程语言可能都会做一下这个。
最近在玩Python，在粗略的看了一下Learning Python和Core Python之后，偶然发现网上有个帖子Python程序员的进化写的很有意思。于是打算仿照一篇，那篇帖子用了十余种方法完成一个阶乘函数，我在这里会用九种不同的风格写出一个Fibonacci函数。
要求很简单，输入n，输出第n个Fibonacci数，n为正整数
下面是这九种不同的风格：
1）第一次写程序的Python程序员：
def fib(n): return nth fibonacci number
说明：
第一次写程序的人往往遵循人类语言的语法而不是编程语言的语法，就拿我一个编程很猛的哥们来说，他写的第一个判断闰年的程序，里面直接是这么写的：如果year是闰年，输出year是闰年，否则year不是闰年。
2）刚学Python不久的的C程序员：
def fib(n):#{
if n<=2 :
return 1;
else:
return fib(n-1)+fib(n-2);
#}说明：
在刚接触Python时，用缩进而非大括号的方式来划分程序块这种方式我是很不适应的，而且每个语句后面没有结束符，所以每次写完一个Python函数之后干的第一件事一般就是一边注释大括号，一边添加漏掉的冒号。
3）懒散的Python程序员：
def fib(n): return 1 and n<=2 or fib(n-1)+fib(n-2)
说明：
看了Learning Python之后，才知道Python没有三元操作符？，不过鉴于Python里bool值比较特殊（有点像C，非零即真，非空即真），再加上Python的逻辑语句也是支持短路求值（Short-Circuit Evaluation）的，这就可以写出一个仿？语句出来。
4）更懒的Python程序员：
fib=lambda n:1 if n<=2 else fib(n-1)+fib(n-2)
说明：
lambda关键字我曾在C#和Scheme里面用过，Python里面的lambda比C#里简便，并很像Scheme里的用法，所以很快就适应了。在用Python Shell声明一些小函数时经常用这种写法。
5）刚学完数据结构的Python程序员：
def fib(n): x,y=0,1 while(n): x,y,n=y,x+y,n-1 return x
说明：
前面的Fibonacci函数都是树形递归的实现，哪怕是学一点算法就应该知道这种递归的低效了。在这里从树形递归改为对应的迭代可以把效率提升不少。
Python的元组赋值特性是我很喜欢的一个东东，这玩意可以把代码简化不少。举个例子，以前的tmp=a;a=b;b=tmp;可以直接用一句a,b=b,a实现，既简洁又明了。
6）正在修SICP课程的Python程序员：
def fib(n): def fib_iter(n,x,y): if n==0 : return x else : return fib_iter(n-1,y,x+y) return fib_iter(n,0,1)
说明：
在这里我使用了Scheme语言中很常见的尾递归（Tail-recursion）写法。Scheme里面没有迭代，但可以用不变量和尾递归来模拟迭代，从而实现相同的效果。不过我还不清楚Python有没有对尾递归做相应的优化，回头查一查。
PS：看过SICP的同学，一眼就能看出，这个程序其实就是SICP第一章里的一个例子。
7）好耍小聪明的Python程序员：
fib=lambda n,x=0,y=1:x if not n else f(n-1,y,x+y)
说明：
基本的逻辑和上面的例子一样，都是尾递归写法。主要的区别就是利用了Python提供的默认参数和三元操作符，从而把代码简化至一行。至于默认参数，学过C++的同学都知道这玩意，至于C#4.0也引入了这东东。
8）刚修完线性代数的Python程序员：
def fib(n): def m1(a,b): m=[[],[]] m[0].append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m[0].append(a[0][0]*b[0][1]+a[0][1]*b[1][1]) m[1].append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) m[1].append(a[1][0]*b[1][0]+a[1][1]*b[1][1]) return m def m2(a,b): m=[] m.append(a[0][0]*b[0][0]+a[0][1]*b[1][0]) m.append(a[1][0]*b[0][0]+a[1][1]*b[1][0]) return m return m2(reduce(m1,[[[0,1],[1,1]] for i in range(n)]),[[0],[1]])[0]
说明：
这段代码就不像之前的代码那样清晰了，所以先介绍下原理（需要一点线性代数知识）：
首先看一下之前的迭代版本的Fibonacci函数，很容易可以发现存在一个变换：y->x, x+y->y。换一个角度，就是[x,y]->[y,x+y]。
在这里，我声明一个二元向量[x,y]T，它通过一个变换得到[y,x+y]T，可以很容易得到变换矩阵是[[1,0],[1,1]]，也就是说：[[1,0],[1,1]]*[x,y]T=[y,x+y]T
令二元矩阵A=[[1,0],[1,1]]，二元向量x=[0,1]T，容易知道Ax的结果就是下一个Fibonacci数值，即：
Ax=[fib(1),fib(2)]T
亦有：
Ax=[fib(2),fib(3)]T
………………
以此类推，可以得到：
Aⁿx=[fib(n),fib(n-1)]T
也就是说可以通过对二元向量[0,1]T进行n次A变换，从而得到[fib(n),fib(n+1)]T，从而得到fib(n)。
在这里我定义了一个二元矩阵的相乘函数m1，以及一个在二元向量上的变换m2，然后利用reduce操作完成一个连乘操作得到Aⁿx，最后得到fib(n)。
9）准备参加ACM比赛的Python程序员：
def fib(n):
lhm=[[0,1],[1,1]]
rhm=[[0],[1]]
em=[[1,0],[0,1]]
#multiply two matrixes
def matrix_mul(lhm,rhm):
#initialize an empty matrix filled with zero
result=[[0 for i in range(len(rhm[0]))] for j in range(len(rhm))]
#multiply loop
for i in range(len(lhm)):
for j in range(len(rhm[0])):
for k in range(len(rhm)):
result[i][j]+=lhm[i][k]*rhm[k][j]
return result
def matrix_square(mat):
return matrix_mul(mat,mat)
#quick transform
def fib_iter(mat,n):
if not n:
return em
elif(n%2):
return matrix_mul(mat,fib_iter(mat,n-1))
else:
return matrix_square(fib_iter(mat,n/2))
return matrix_mul(fib_iter(lhm,n),rhm)[0][0]
说明：
看过上一个fib函数就比较容易理解这一个版本了，这个版本同样采用了二元变换的方式求fib(n)。不过区别在于这个版本的复杂度是lgn，而上一个版本则是线性的。
这个版本的不同之处在于，它定义了一个矩阵的快速求幂操作fib_iter，原理很简单，可以类比自然数的快速求幂方法，所以这里就不多说了。
PS：虽然说是ACM版本，不过说实话我从来没参加过那玩意，毕竟自己算法太水了，那玩意又太高端……只能在这里YY一下鸟~
python中，最基本的那种递归（如下fib1)效率太低了，只要n数字大了运算时间就会很长；而通过将计算的指保存到一个dict中，后面计算时直接拿来使用，这种方式成为备忘(memo)，如下面的fib2函数所示，则会发现效率大大提高。
在n=10以内时，fib1和fab2运行时间都很短看不出差异，但当n=40时，就太明显了，fib1运行花了35秒，fab2运行只花费了0.00001秒。
n=40时，输出如下：
jay@jay-linux:~/workspace/python.git/py2014$ python fibonacci.py 2014-10-16 16:28:35.176396 fib1(40)=102334155 2014-10-16 16:29:10.479953 fib2(40)=102334155 2014-10-16 16:29:10.480035
这两个计算Fibonacci数列的函数，如下：https://github.com/smilejay/python/blob/master/py2014/fibonacci.py
import datetime
def fib1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib1(n - 1) + fib1(n - 2)
known = {0: 0, 1: 1}
def fib2(n):
if n in known:
return known[n]
res = fib2(n - 1) + fib2(n - 2)
known[n] = res
return res
if __name__ == '__main__':
n = 40
print(datetime.datetime.now())
print('fib1(%d)=%d' % (n, fib1(n)))
print(datetime.datetime.now())
print('fib2(%d)=%d' % (n, fib2(n)))
print(datetime.datetime.now())
后记：
由于刚学习Python没多久，所以对其各种特性的掌握还不够熟练。与其说是我在用Python写程序，倒不如说我是在用C，C++，C#或是Scheme来写程序。至于传说中的Pythonic way，我现在还没有什么体会，毕竟还没用Python写过什么真正的程序。
Learning Python和Core Python都是不错的Python入门书籍，前者更适合没有编程基础的人阅读。
Python是最好的初学编程入门语言，没有之一。所以它可以取代Scheme成为MIT的计算机编程入门语言。
热AI工具
Undresser.AI Undress
人工智能驱动的应用程序，用于创建逼真的裸体照片
AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。
Undress AI Tool
免费脱衣服图片
Clothoff.io
AI脱衣机
Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸！
热门文章
热工具
记事本++7.3.1
好用且免费的代码编辑器
SublimeText3汉化版
中文版，非常好用
禅工作室 13.0.1
功能强大的PHP集成开发环境
Dreamweaver CS6
视觉化网页开发工具
SublimeText3 Mac版
神级代码编辑软件(SublimeText3)
PHP和Python：解释了不同的范例
Apr 18, 2025 am 12:26 AM
PHP主要是过程式编程，但也支持面向对象编程（OOP）；Python支持多种范式，包括OOP、函数式和过程式编程。PHP适合web开发，Python适用于多种应用，如数据分析和机器学习。
在PHP和Python之间进行选择：指南
Apr 18, 2025 am 12:24 AM
PHP适合网页开发和快速原型开发，Python适用于数据科学和机器学习。1.PHP用于动态网页开发，语法简单，适合快速开发。2.Python语法简洁，适用于多领域，库生态系统强大。
PHP和Python：深入了解他们的历史
Apr 18, 2025 am 12:25 AM
PHP起源于1994年，由RasmusLerdorf开发，最初用于跟踪网站访问者，逐渐演变为服务器端脚本语言，广泛应用于网页开发。Python由GuidovanRossum于1980年代末开发，1991年首次发布，强调代码可读性和简洁性，适用于科学计算、数据分析等领域。
Python vs. JavaScript：学习曲线和易用性
Apr 16, 2025 am 12:12 AM
Python更适合初学者，学习曲线平缓，语法简洁；JavaScript适合前端开发，学习曲线较陡，语法灵活。1.Python语法直观，适用于数据科学和后端开发。2.JavaScript灵活，广泛用于前端和服务器端编程。
sublime怎么运行代码python
Apr 16, 2025 am 08:48 AM
在 Sublime Text 中运行 Python 代码，需先安装 Python 插件，再创建 .py 文件并编写代码，最后按 Ctrl B 运行代码，输出会在控制台中显示。
vs code 可以在 Windows 8 中运行吗
Apr 15, 2025 pm 07:24 PM
VS Code可以在Windows 8上运行，但体验可能不佳。首先确保系统已更新到最新补丁，然后下载与系统架构匹配的VS Code安装包，按照提示安装。安装后，注意某些扩展程序可能与Windows 8不兼容，需要寻找替代扩展或在虚拟机中使用更新的Windows系统。安装必要的扩展，检查是否正常工作。尽管VS Code在Windows 8上可行，但建议升级到更新的Windows系统以获得更好的开发体验和安全保障。
vscode在哪写代码
Apr 15, 2025 pm 09:54 PM
在 Visual Studio Code（VSCode）中编写代码简单易行，只需安装 VSCode、创建项目、选择语言、创建文件、编写代码、保存并运行即可。VSCode 的优点包括跨平台、免费开源、强大功能、扩展丰富，以及轻量快速。
notepad 怎么运行python
Apr 16, 2025 pm 07:33 PM
在 Notepad 中运行 Python 代码需要安装 Python 可执行文件和 NppExec 插件。安装 Python 并为其添加 PATH 后，在 NppExec 插件中配置命令为“python”、参数为“{CURRENT_DIRECTORY}{FILE_NAME}”，即可在 Notepad 中通过快捷键“F6”运行 Python 代码。
