再帰は難しいと思われているようだ。たとえば、Joel Spolsky 氏はJavaスクールの危険で以下のようなことを書いている。
私のささやかな経験から言わせてもらうと、伝統的に大学のコンピュータサイエンスのカリキュラムで教えられているもので、多くの人がうまく理解できないものが2つあった: ポインタと再帰だ。
再帰が難しいと思われている理由を私なりに分析したいと思う。このドリルを終えた人なら、再帰に「ループと同等の再帰」と「ループを超えた再帰」があること理解したはずである。
もし「ループと同等の再帰」が難しいのであれば、それは単によい入門書に出会わなかったからである。
もし「ループを超えた再帰」が難しいのであれば、それは再帰が難しいのではなく、問題自体が難しいのだ。
この「再帰ドリル」は、「よい入門書があれば、再帰の習得はそれほど難しくない」という信念の下に書かれた。再帰を系統立てて包括的に扱った。「ループと同等の再帰」は簡単に理解できるように、「ループを超えた再帰」は理解が不可能でないように、注意して説明したつもりだ。
再帰を大きな山に例えると、このドリルを終えた人は、8合目ぐらいまでは登ったことになる。ここまでの景色で満足できるなら、あとはたくさんの練習と実践での利用あるのみだ。もっと高みを目指すなら、例えば多相再帰のような特殊な分野にも足を踏み入れる必要がある。
もっと勉強するための指針を以下に示そう。
-
再帰がある程度分かったら、再帰をなるべく使わないで、高階関数を用いた部品プログラミングを学ぼう。そちらの方が、コードが明瞭になる。再帰の勉強はなんだったのかと思う人もいるかもしれないが、高階関数は再帰を使って書かれている。単に部品を使うだけのプログラマから、いざとなれば部品を自作できるプログラマになった訳だ。このテーマを学ぶにはプログラミングHaskellがいいだろう。
-
リストに関する再帰を学ぶためには、HaskellのData.Listを冒険してみるのがいいだろう。説明と型のみから、実装を考えるのは実によい訓練になる。
-
二分探索木を平衡させる方法について学ぼう。平衡させるには「木の回転」という知識が必要になる。平衡木としては AVLや赤黒木が有名だが、Haskell の Data.Set では重み平衡木(weight balanced tree)が採用されている。
-
平衡探索木が完成したら、効率のよい集合演算(和集合、共通部分、差集合)の実装に挑戦してみよう。
-
探索木の親戚であるヒープ(優先順位付きキュー)を学ぼう。関数プログラミングの楽しみの第一章に「ねじれヒープ」(Skew heap)が載っている。二項ヒープ(二分ヒープと間違えないように)についても調べてみるといいだろう。
-
多相再帰を理解するためには、フィンガーツリーを調べよう。Haskellでの実装は、Data.Sequenceである。