不改變內(nèi)存限制用遞歸實(shí)現(xiàn)斐波拉契

//實(shí)現(xiàn)斐波拉契數(shù)列

function flist($limit){
    $pre1 = 1;
    $pre2 = 1;
    for ($i=0; $i <$limit ; $i++) {
        if($i<2){
            yield 1;
            continue;
        }
        $now = $pre2+$pre1;
        $pre2 = $pre1;
        $pre1 = $now;
        yield $now;
    }
}

$flist = flist(10);
foreach ($flist as $key => $value)
{
    echo $value . "\n";
}

可以使用 yield 協(xié)程調(diào)用來(lái)實(shí)現(xiàn)

第二種方案使用全局變量$cache作為緩存，所以再遞歸中每一個(gè)n對(duì)應(yīng)的值只計(jì)算一遍，事實(shí)上計(jì)算fib(x)只會(huì)調(diào)用x次函數(shù)，可以在很快的時(shí)間和很小的棧空間使用下完成。