再帰の最適化

将棋の世界で『再帰的手順』などと言っても、よほどの詰将棋マニアしか知らないだろうが、プログラマならば馴染みのある概念だろう。

詰将棋にハノイの塔のような再帰的手順を導入して長手数の詰将棋を作るわけである。長手数の詰将棋はそれ自体が価値があるので、ここにハノイの塔のような手順が入り込めれば、指数的な手数の超巨大長編が完成するかも知れない、というわけである。たとえば、「寿限無」がそうだ。

http://ztrhome.cside.com/yomimono/yomgen01/yomsaiki/yomsaiki.html

 協力詰においては呼び出しハガシと言う形で部分的に再帰手順が表れました。

それを明確な形で表し、19447手という超長手数で実現したのが、加藤徹氏の

「寿限無」でした。

ところで、ハノイの塔は再帰的な手順で解く方法がポピュラーだが、これを非再帰的に解く方法もある。私は15年ぐらい前に奥村先生の「C言語による最新アルゴリズム事典」(ASIN:4874084141)で見て、衝撃を受けた。この本には、どうやってそのアルゴリズムを導いたのかについては書かれていなかったので、一種の謎解きとしてそれを導出することを考えたものだった。

しかし結局のところ再帰を非再帰形になおせるのは、関数の末尾で自分自身を呼び出す、末尾再帰(tail recursion)と呼ばれるものが主で、それ以外の再帰的呼び出しの非再帰化は難しい。ハノイやらフィボナッチ数列程度ならばともかく、一般的には変換不可能だと思う。実用上は、末尾再帰が一番多いのでそれでもあまり問題にはならないのだが、prologにせよ、lispにせよ、再帰を関数記述の根幹に据えなければならない言語では、このへんが結構深刻な問題だと思う。まあ、lisp系の言語は最初から速度は諦めている意味もあるのだが．．。