今やこれは逆ではないか。

再帰的アルゴリズム
  • まずは，非再帰プログラムで問題を考えてみる。
  • 難しいと判断した場合，再帰プログラムで考えてみる。

むしろ私はこうしてきた。

  • まずは再帰で実装する。
  • 速度と資源の制約があるとき、非再帰で実装しなおす

一番の理由は、今やプログラミングそのもののコストの方がプログラムを実行するコストよりも大きいからだ。早くプログラムを書く要請の方が速いプログラムを書く要請より強いからだ。

次の理由は、再帰は遅いとは限らないからだ。特にLisp系では、末尾再帰(tail recursion)は重くない。これはもうshiroさんが力説しているのでそちらを参照して欲しい。フィボナッチ数列を解くプログラムはとにかく、階乗を解くプログラムぐらいだとわざわざ再帰しないようにするご利益はあまりないのだ。

さらに、フィボナッチ数列のようなプログラムに関しても、メモ化(Memoize)という手段がある。一度計算した値は、計算せずメモを見るだけにするのだ。

fib( ) = 55

たいていのLightweight Languageではこのメモ化は簡単に実装できる。Javascriptでは以下のとおり。

function memoize(methname, obj){
  if(!obj) obj = window;
  if(!(methname in obj)){
    throw new Error("No '" + methodname + "' method in object " + obj);
  }
  var f = obj[methname];
  var cachename = "_memoize_" + methname;
  obj[cachename] = {};
  obj[methname] = function(){
    var k = [];
    for(var i = 0; i < arguments.length; i++) k[i] = arguments[i];
    if(!(k in this[cachename])) this[cachename][k] = f.apply(this, arguments);
    return this[cachename][k];
  };
  return cachename;
}

使い方は以下のとおり。

function fib(n){
  return n <= 2 ? 1 : fib(n-2)+fib(n-1)
}
memoize('fib');

Structure and Interpretation
of Computer Programs
 H. Abelson / G. Sussman / J. Sussman
[邦訳:計算機プログラムの構造と解釈]

これでもまだ実は速度もメモリーも非再帰版の方が速いのだが、たいていの目的ではこれで充分な速度が出る。

実際再帰は、こういった簡単な関数ばかりではなく、再帰的な構造をしたデータを処理するのに非常に向いている。例えばHTMLなどの言語のトップダウンパーザーは、再帰なしで書くのは非常に大変だ。

とはいえ、上のfibを実行してもらえばわかるとおり、あまりに多い再帰は言語の実装の方で嫌う場合も多い。safariでは100未満で文句を言われるし、firefoxでも1000で文句を言われる。それに対し、bsearchやqsortなど、「問題を分割してせめる」タイプの再帰関数では、せいぜい数十段程度の再帰ですむ。

今や「再帰アレルギー」は功より罪の方が多いと思う。もはやノートパソコンにもGBクラスのメモリーを積んでいる今、もっと積極的に再帰を評価すべきだと思うのだが。再帰アレルギーの人は、是非↑のSICPでも読んで治療に励んでいただきたい。

Dan the Recursive Man