<?php
/**
 * 斐波那契数列：1 1 2 3 5 8 13 21 34 55 …
 * 概念：
 *  前两个值都为1，该数列从第三位开始，每一位都是前两位的和
 *
 * 规律公式为：Fn = F(n-1) + F(n+1)
 *
 * 第一种思路：使用递归实现
 *
 * 优点：易理解，容易变成
 * 缺点：由于是递归是用栈机制实现的，每深入一层都要占去一块栈数据区域，对嵌套层数深的一些算法递归会力不从心，在空间上会以内存崩溃或超时而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销，所以在深度大的时候递归的时空性不好
 */

// 记录开始时间
$start_time = microtime(true);

$n = 30;
$res = Fibonacci($n);
print_r($res);

// 记录结束时间
$end_time = microtime(true);

// 记录耗时时间
echo round($end_time - $start_time, 3) . ' 秒';

/**
 * 实现斐波那契数列
 * @param $n
 * @return array|bool
 */
function Fibonacci($n)
{
    if ($n < 1) {
        return false;
    }

    $res = [];
    for ($i = 1; $i <= $n; $i++) {
        $res[] = Fib($i);
    }
    return $res;
}

/**
 * 获得斐波那契数列，第N位的数字
 * @param $n
 * @return int
 */
function Fib($n)
{
    // 如果是第一位和第二位的话，则返回1
    if ($n == 1 | $n == 2) {
        return 1;
    }

    return Fib($n - 1) + Fib($n - 2);
}