再帰アルゴリズムの計算量
再帰アルゴリズムだからといってすぐにオーダーは決まらない。問題による。
例えばフィボナッチ数を求める場合。
F(n) = F(n-1) + F(n-2)
においてF(n)はn番目のフィボナッチ数を表すとする。
n番目のフィボナッチ数を計算するためには、F(n-1)とF(n-2)を計算するために、さらにF(n-2)とF(n-3)、F(n-3)とF(n-4)....を計算する必要がある。F(n-1)とF(n-2)で2つの計算をnの深さ分だけ繰り返す。よって計算量はO(2^n)になる。