費波那契數列

在這個練習中，你要實作自然界中隨處可見的 費波那契數列（Fibonacci sequence）。這個數列長這樣：「0, 1, 1, 2, 3, 5, 8…」。你會用一個能產生此數列的遞迴演算法來實作。

前兩個數是 0 和 1，之後的每個數都是前兩個數之和。

我們可以用遞迴來定義這個數列：$fib(n)=fib(n-1)+fib(n-2)$，其中 \(fib(0)=0\) 且 $fib(1)=1$，而 \(n\) 表示數列中的第 \(n\) 個位置。

在第一步，你會用遞迴來撰寫費波那契。第二步，你會用動態規劃來改良它，將子問題的解存到 cache 變數中。