# PHP 与斐波那契数列

## 三种方式实现斐波那契数列

### 普通递归实现

``````function fibonacci_recursive(\$n) {
if (\$n <= 1) {
return 1;
}

return fibonacci_recursive(\$n - 1) + fibonacci_recursive(\$n - 2);
}

for (\$i = 1; \$i <= 30; \$i++) {
echo fibonacci_recursive(\$i) . "  ";
}

3.52s user 0.00s system 99% cpu 3.521 total
``````

### 递归优化，增加内存缓存

``````function fibonacci_recursive_optimization(\$n) {
static \$caches_arr = [];

if (isset(\$caches_arr[\$n])) {
return \$caches_arr[\$n];
}

if (\$n <= 1) {
\$res = 1;
} else {
\$res = fibonacci_recursive_optimization(\$n - 1) + fibonacci_recursive_optimization(\$n - 2);
}

\$caches_arr[\$n] = \$res;

return \$res;
}

for (\$i = 1; \$i <= 30; \$i++) {
echo fibonacci_recursive_optimization(\$i) . "  ";
}

0.01s user 0.01s system 98% cpu 0.022 total
``````

### 闭包实现

``````function fibonacci_closure() {
static \$x = 0;
static \$y = 1;
return function () use (&\$x, &\$y) {
[\$x, \$y] = [\$y, \$x + \$y];
return \$y;
};
}

\$f = fibonacci_closure();
for (\$i = 1; \$i <= 30; \$i++) {
echo \$f() . " ";
}

0.02s user 0.01s system 99% cpu 0.030 total``````
《L02 从零构建论坛系统》

《L03 构架 API 服务器》

7个月前

@rufo 欢迎贴出来实现

7个月前
``````function getNum(\$n) {
\$num = 0;
\$pre = 1;
while (\$n--) {
\$num += \$pre;
\$pre = \$num - \$pre;
}
return \$num;
}``````
7个月前

4个月前

``````function recursionCache(\$i)
{
static \$cache = [
1 => 1,
2 => 1,
];

if (!isset(\$cache[\$i])) {
\$cache[\$i] = recursionCache(\$i - 2) + recursionCache(\$i - 1);
}

return \$cache[\$i];
}``````
3个月前

``````function recursionCache(\$i)
{
\$f = 0;
\$g = 1;
// f(n) = f(n+1) - f(n-1)
while (\$i > 0) {
\$g += \$f;
\$f = \$g - \$f;
\$i--;
}

return \$f;
}``````
3个月前

3

1

48

6