斐波那契数列：

       经典数学问题之一；斐波那契数列，又称黄金分割数列，指的是这样一个数列：

  1、1、2、3、5、8、13、21、……

看到这个数列大家很容易就推算出来后面好几项的值，那么到底有什么规律，简单说，就是前两项的和是第三项的值，也许你会想到的是迭代，也许你想到的是递归。

PHP 使用递归实现斐波那契数列代码如下：

<?php
// 使用递归实现斐波那契数列
function fibon($n){
    if ($n <= 2) {
        return 1;
    }
    return fibon($n - 1) + fibon($n - 2);
}

如果把已经算过的值，保存起来下次直接用的话，递归次数就会明显减少。优化代码如下：

<?php
// 优化后的递归
function fibonac($one, $two, $n){
    if ($n > 2) {
        return fibonac($one + $two, $one, $n - 1);
    }
    return $one;
}

可以通过统计递归次数来看看两种方法递归的次数

<?php
// 使用递归实现斐波那契数列
function fibon($n){
    global $num1;
    $num1++;
    if ($n <= 2) {
        return 1;
    }
    return fibon($n - 1) + fibon($n - 2);
}

// 优化后的递归
function fibonac($one, $two, $n){
    global $num2;
    $num2++;
    if ($n > 2) {
        return fibonac($one + $two, $one, $n - 1);
    }
    return $one;
}

echo fibon(8);
echo "<br> 递归次数 $num1";
echo "<br>";
echo fibonac(1, 1, 8);
echo "<br> 递归次数 $num2";

使用迭代实现斐波那契数列

<?php
// 使用迭代
function fibonacci($n) {
    $ret = [];

    for ($i = 0; $i <= $n; $i++) {
        if ($i == 0) {
            $ret[$i] = 0;
            continue;
        } else if ($i == 1) {
            $ret[$i] = 1;
            continue;
        }

        $ret[$i] = $ret[$i - 1] + $ret[$i - 2];
    }

    return $ret[$n];
}
$n = 8;
echo fibonacci($n);

递归优化，增加内存缓存

<?php
function recursionCache($i) {
    static $cache = [
        1 => 1,
        2 => 1,
    ];

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

    return $cache[$i];
}