再帰の適切でない使い方

はじめに

再帰処理万能論者だったのですが、再帰処理の弱点が見つかってしまったため共有します。

計算量の問題

計算量の問題が発生したのは以下のコードです。

fibonacci :: Int -> Int
fibonacci 0 = 0
fibonacci 1 = 1
fibonacci num = fibonacci (num - 1) + fibonacci (num - 2)

あるいは、

def fibonacci(num)
  case num
  when 0
    return 0
  when 1
    return 1
  else
    fibonacci(num - 1) + fibonacci(num - 2)
  end
end

このコードの実行速度が明らかに遅いんですよね。

そこで、計算量を考えてみました。

実例で考えてみる

1. fibonacci(3)の例

fibonacci(3) = fibonacci(2) + fibonacci(1)
= fibonacci(1) + fibonacci(0) + fibonacci(1)
計算量は

1. fibonacci(1)
2. +
3. fibonacci(0)
4. +
5. fibonacci(1)

で、5ステップですね。

2. fibonacci(4)の例

fibonacci(4) = fibonacci(3) + fibonacci(2)
= 5ステップ + fibonacci(1) + fibonacci(0)
= 5ステップ + 3ステップ
計算量は

1. 5ステップ
2. +
3. 3ステップ

で、9ステップですね。

計算量はどの程度増えているでしょうか？

9 / 5 = 1.8、1.8倍の計算量ですね。

これ以降も考えてみると
fibonacci(5)は15ステップ
fibonacci(6)は25ステップ
25 / 15 = 1.66...
数が大きくなるにつれ、だんだんと収束していきます。

最終的には(1 + √5) / 2（約1.618）になるようです。

この時の計算量をO(Φ^n) Φ=(1+√5)/2と書きます。
あるいは、シンプルに考えてO(2^n)でもいいでしょう。

まあ、数値はどうでもいいのです。
重要なことは、「計算量が指数関数的に増えていく」ということです。

指数関数的に増えていく

考えてみれば当たり前ですね。関数を実行する事に2度、自身を呼び出しており、毎回新しい計算をしているので。
（fibonacci(n - 1)） fibonacci(n-2)の2度）

そこで、以下のように書き換えて、すでに行った計算を行わないようにして解決しました。
新規の計算は、末尾を追加する時だけです。これをメモ化と言うらしい。

これで計算量はO(n)になります。

fibonacci :: Int -> Int
fibonacci n = fibs !! n
  where
    fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

なお、フィボナッチ数列についてはiterate（反復処理）でも書けます。
rubyのtimesやJSのforなどですね。
泥臭いやり方だと思っていたんですが、計算量は「メモ化した再帰処理」と同等です。

計算量以外の問題

もう一つの問題、それは「スタックオーバーフロー」です。

スタックとは「関数やメソッドを呼び出して、一時的に保存する場所」です。それがいっぱいになって、溢れちゃうんですね。

スタックオーバーフローのイメージ

先ほども出した例ですが
fibonacci(3) = fibonacci(2) + fibonacci(1)です。
このとき、fubonacci(2)はまだ分解されて、fibonacci(1) + fibonacci(0)になります。
この時、最初にあったfibonacci(1)はどうなるでしょう・・・

実行されるまで、保持されるわけですね。
この例では3という小さい数字なので問題は起きていませんが、
これが10だったら・・・？
fibonacci(10) = fibonacci(9) + fibonacci(8)
= fibonacci(8) + fibonacci(7) + fibonacci(7) + fibonacci(6)
= fibonacci(7) + fibonacci(6) + fibonacci(6) + fibonacci(5) + fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4)
...
と、すでに恐ろしい数のスタックが発生しています。

これをうまく処理できる言語とできない言語があります。

処理できる言語（スタックオーバーフローが発生しない）

• JavaScript（末尾呼び出し最適化が導入されたもの）
• Haskell（遅延評価）

処理できない言語

• Ruby

言語の違いも意識して再帰を使用するのが良いですね。

おわりに

さて、次は何を書こうかしら・・・

参考