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

[Jakesoft]

实习时面试面到这个问题，当时还不知道斐波那契数列，讲给同学听时，他说，这不就是斐波那契数列吗？！ (尴尬脸）

然后这是我面试的回答:

$total = [0, 1];

for ($i = 2; $i < 100; $i++)
{
	$total[] = $total[$i - 1] + $total[$i - 2];
}

今天看到别人（书本）的实现，需要定义几个变量来交换当前值、上一个值，感觉好麻烦。

还有我的代码应该没啥问题吧

[laoyuan]

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

[superYy]

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

[misaka19000]

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

[GPIO]

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

[superYy]

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

[gisonrg]

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

[mrgeneral]

算法没啥问题啊。

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

[SteveLee]

矩阵快速 mi

[dtfm]

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

[em2046]

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

[akira]

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

[q397064399]

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

[q397064399]

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

[q397064399]

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

[loggerhead]

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

[xjp]

没有问题

[assad]

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)]

[Kilerd]

@loggerhead

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

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

[loggerhead]

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

[Contextualist]

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