yjiang's cake

递归方式

时间复杂度: O(2^n)

function fib($n){
    if( in_array($n, [0, 1]) ) return $n;
    return fib($n-1) + fib($n-2);
}

迭代方式

时间复杂度: O(n), 空间复杂度: O(1)

function fib($n){
    if( in_array($n, [0, 1]) ) return $n;
    $f0 = 0;
    $f1 = 1;
    $f2 = null;
    for($i=0; $i<$n; $i++){
        $f2 = $f0 + $f1;
        $f0 = $f1;
        $f1 = $f2;
    }
    return $f2;
}