【Python】フィボナッチ数列の実装

現在Recursionに取り組んでいる。 そこで学んだことをメモする。

---

フィボナッチ数列

次の漸化式で表現される数列をフィボナッチ数列と呼ぶ。 計算量はO(2ⁿ)である。

F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (n ≥ 2)

ja.wikipedia.org

フィボナッチ数列は自然界でも観測される数列で、黄金比とも関係が深い。 そのため非常に重要な数列の一つとして扱われている。

www.nli-research.co.jp

実装

実装自体は簡単で、漸化式をコードに落とし込めば良い。 その際、再帰の考え方を用いる。

def fib(n):
  if n == 0: return 0
  if n == 1: return 1

  return fib(n - 1) + fib(n - 2)

再帰処理の実装のコツは以下で記載している。

note-tmk.hatenablog.com

末尾再帰の考えを用いた改良

末尾再帰

再起呼び出しをする関数の引数に計算結果も渡すことにより、 スタックに計算で使用している容量を確保することなく 効率的に計算できる。

実装

# 末尾再帰を用いたフィボナッチ数列改良
def fib(n):
    return fib_helper(0, 1, n)

def fib_helper(n1, n2, n):
    if n < 1:
        return fib_updated(n2, n1 + n2, n - 1)

フィボナッチ数列は計算量が大きいため、 nに与えられる数値が大きい場合最悪計算できないケースがある。

空間計算量が多い理由は、スタックにn-1分の結果が保存されるためである。 時間計算量が多い理由は（特にキャッシュが効いていない場合）2の指数関数的に 計算量が増えるためである。（fib(n)を計算するためにはfib(n-1)とfib(n-2)を計算する必要がある）

そこで末尾再帰という考え方を用いると、 空間・時間計算量両方とも劇的に削減できる。