我是这么实现斐波那契数列的

新年刚开始又来黑 PHP 。。总之不用递归都是好的

性能低！应该创建一个缓冲数组存贮之前的值

还行，不过不是非得用数组吧

中学学数列的时候都会讲到斐波那契数列的啊，你是不是当时没好好听课。。。

@superYy 没仔细看，之前说错了

不用数组只用两个变量可以省空间→_→

算法没啥问题啊。

前面的存下来没啥意义， echo 输出了吧，换成俩变量，节省空间。

矩阵快速 mi

fib 不应该这样么？ a, b = b , a+b

没毛病
为啥不用递归呢
PS ：递归也可以不是 O(2^n)

没问题。只是当 N 比较大的时候，会略尴尬

@em2046 空间复杂度为 O(2^n) 递归过深，直接爆栈，所以才有了 stackoverflow.com

@em2046 递归调用每一次 call ，按照计算机的函数堆栈模型，栈帧要向下延伸，然后栈容量不够用的时候，就直接爆了

一般问菲波那切数列的话，都会接着问 栈溢出的问题，
如果不知道函数递归调用过深导致的爆栈问题，就会略显尴尬了

可以看看我这篇文章求 Fibonacci 数列的 N 种算法： https://loggerhead.me/posts/qiu-fibonacci-shu-lie-de-n-chong-suan-fa.html

没有问题

import numpy

def mm_fib(n):
return (numpy.matrix([[2,1],[1,1]])**(n//2))[0,(n+1)%2]

[mm_fib(i) for i in range(20)]

@loggerhead

> 重复平方技术也可以用在求 Fibonacci 数上。

可行吗？？ 我想了一下，好像没有什么思路。 求指点。

@Kilerd 文章中有写。比如： 2^8 = 2^4 * 2^4 就只用算一次 2^4 和一次乘法，时间复杂度降到了 O(logn)

@Kilerd 文章中下面的矩阵乘法和代数方法就是“重复平方”（其实就是乘法结合律）的具体实现

话说如果只是要求求出某一个 Fibonacci 数而不是整个数列的话，可以直接用公式在 O(1)的时间内求得。

@Kilerd 线性递推先构造出矩阵，然后用矩阵乘法结合律降次

我记得高一时上课时无聊吧这玩意儿通项公式求出来了。。

@raysonx 公式里面全是无理数，计算机直接算不好吧

@loggerhead 重复平方，我懂。

@Contextualist @xiaopc GET 到了。 矩阵方法确实神奇。 至于代数方法，感觉是像是把矩阵方法拆开些而已。

完蛋了，现在看博客都专心不了了。

这个面试比较蛋疼，他是要考察你什么呢？斐波拉契数列的定义？还是高效的代码实现？

@raysonx 我想了一下没想出来怎么在 O(1)时间内求出来。通项是无理数，比如 n 很大，算出来的精度就很可疑了。有什么好方法吗？ O(1)

@q397064399 尾递归打开优化 没区别

@GPIO 可能是忘记了吧，不过大学确实很少上课。。。

@Cbdy 快速矩阵幂， O(logn)

@chuanqirenwu 应该是如何实现“后面一个数等于前两个数之和”吧，至于如何高效实现我还需要花点功夫。

会 Google ，你就离大牛近了一步。

@loggerhead 弱弱问一下，你的博客文章中矩阵为什么乘在向量的右边？

看下 sicp 里面就有，树形递归和线性迭代，书上讲两种过程的优缺点说的很清楚

@q397064399 这么浅显的问题要是面试官顺着你的思路真的问了那只能恭喜你局面被你控制了

@bdbai 这不是矩阵乘法吗？ 1x2 乘以 2x2 的矩阵 = 1x2 的矩阵。你可以看看这个： http://www.ruanyifeng.com/blog/2015/09/matrix-multiplication.html

用矩阵，斐波那契的复杂度是 O （ log （ n ））

用通项公式...

@j5shi 我会说很多程序员 并不知道 程序堆栈这回事么？

@q397064399 尝试尾递归呢

@longhao 主要看汇编层面的优化吧，毕竟生成机器码，底层是怎么运作的，高级语言很难解释清楚
一般是不推荐使用过深的递归，

说到斐波那契数列，大家肯定记得“生兔子问题”。题目很绕。

一只小兔子，出生三个月变大兔子，变成大兔子后每个月生一只小兔子；
小兔子三个月后也能变成大兔子开始生小兔子。
问 n 个月后一共有几只兔子。

我完全被搞蒙了这尼玛什么鬼。
我还觉得这题目有歧义啊，比如说长成大兔子的当月就能生小兔子吗还是下个月才能生小兔子。
你想啊，这个月长成大兔子，难道不需要怀胎一个月吗？
然后生兔子我们是不是按一半男一半女算？两只兔子一个月生一只才对吧？
然后我还在想兔子真的繁殖能力这么强吗？

然后我画了一下午“生兔子”的图。
然后我还用了各种奇怪的方法模拟兔子成长过程什么的，总之这题没写出来。

后来才知道这就是斐波那契数列。迭代 a, b = b, a + b 就行了。
然后我就觉得，要考斐波那契就老老实实的说你要考斐波那契，我会就是会，不会我就学。
求你不要搞些奇奇怪怪的描述来忽悠人了

@loggerhead 按照阮老师的写法，变换矩阵乘在向量左边的，高中数学书上也这么写......

@bdbai 没搞懂你什么意思……矩阵乘法不满足交换律的，所以如果我写反了，那么我就写错了，但是我仔细看了看，好像没问题啊……

@loggerhead 抱歉我看错了，原来是横着写的

@bdbai 哈哈

@MayLava 这种题目考察的是语言理解能力，这么 简单的描述都没看懂，以后读产品经理的需求怎么办？（手动滑稽

@blackjar fib 要求 n-1 和 n-2 ，不是尾递归
如果是存在尾递归，则必然可以重写为循环，因为编译器就是这么干的