[Algorithm] 以空間換取時間(以Fibonacci為例)

一般在寫程式會在意的效率的決定因素，在於花費時間以及記憶體用量。
以Fibonacci數列來說，大部分的書寫遞迴的方式會像這樣：

int fib(int n)
{
  if(n <= 1) return n;
  return fib(n-1) + fib(n-2);
}

在這種狀況下，同樣的值會被重複的運算，
比如fib(8) = fib(7) + fib(6)，fib(7) = fib(6) + fib(5)，
fib(6)就變成重複計算了。

當然，有些compiler據說會很聰明地自己去列表來記錄，
這樣碰上有記錄的就直接把值丟上去而不用重算；
但如果不想把效率給不知道會不會幫忙的compiler決定的話，
自己修改一下程式碼，其實也可以達到效果的！

比如把程式改成以下這樣：

int fibs[n+1]; // 宣告一個陣列來記已經算過的數值

int fib(int n)
{
  if(n <= 1) return n;
  if(fibs[n] != 0) return fibs[n]; // 已經算過的就直接回傳值
  return fibs[n] = fib(n-1) + fib(n-2);
}