PHP: Fibonacci Sequence

Finbonacci Sequence (費氏數列、費伯納數列) 對於寫程式的人來說應該不陌生。數學上的費氏數列是以遞迴方式定義的，如下

F0 = 0, F1 = 1 時，Fn = Fn-1 + Fn-2

用文字來說，就是費氏數列由 0 和 1 開始，之後的費氏數列就由之前的兩數相加。前幾個數字是

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377.....

用遞迴方式的標準寫法是…

<?php
function fib($n){
    if($n == 0) return 0;
    if($n == 1) return 1;
    return fib($n-1) + fib($n-2); // 只有return，沒有echo
}

for($i = 0; $i <= 10; $i++){
    echo fib($i).' '; // 實際上輸出數列
}
?>

0 1 1 2 3 5 8 13 21 34 55

但是用這種方法才能看到數列也太瞎了，所以想改成計算過程中就輸出數列的版本，想不到這問題還真的要思考一下…. 最後的成果如下….

<?php
function fib($n, $output = true){
    if($n == 0){
        if($output) echo '0 ';
        return 0;
    }
    if($n == 1){
        if($output){
            fib(0, true);
            echo '1 ';
        }
        return 1;
    }
    $a = fib($n-1, $output);
    $b = fib($n-2, false);
    $sum = $a + $b;
    if($output) echo $sum.' ';
    return $sum;
}

fib(10);
?>
0 1 1 2 3 5 8 13 21 34 55

同樣的題目用 for loop 寫倒是蠻簡單的

<?php
function fib_in_loop($x){
    $sum = 0;
    $a = 0;
    $b = 1;
    for($i = 0; $i < $x; $i++){
        printf('%d ', $b);
        $sum = $a + $b;
        $a = $b;
        $b = $sum;
    }
    return $sum;
}

fib_in_loop(10);
?>
0 1 1 2 3 5 8 13 21 34 55