概念的説明


† 再帰関数をご存知なら、この区画は飛ばしてかまいません。

再帰関数(リカーシブ ファンクション)は計算理論に用いられて、計算機科学でもよく取り上げられるようだ。
このリカーシブ recursiveの日本語訳としては"帰納"もある。数学的帰納法の帰納であるが、これは論理的な推論としての帰納(induction)ではないので混乱する。高校数学で出会う"漸化式"もリカーシブ リレーションである。
名詞の"再帰"は電算系ではrecursion、動詞の"再帰する"はrecurであり、forthのワードrecurseは英単語ではないようである。

これは要するに数列である。数列は、順番を表す整数ないし自然数を定義域とした、ステップ番号値の関数として考えられるわけだが、その場合に、数列の各値が、当の数列の前のステップの値(複数もあり得る)との数式的関係によって定まるものが、再帰関数である。そこに初期値を与えると、その数式的関係に従って一挙に数列全体が決まり、関数が定義されるというわけである。

数列やステップ関数が出てくるのは、ひとつには漸化式、また数学的帰納法の関連、そして解析学の数列(級数)がある。これらは番号付き系列という意味で形式的には似ているが、着目点がだいぶ異なる。解析学(微分積分)では数列や級数が収束するかどうかが非常に重要な要素である。他方、漸化式では、再帰的な関係を解いてステップ値nだけの関数に還元してしまうことが主な問題であり、数学的帰納法では初期値を与えれば全体が決まる関係を示すというところが重要である。

計算機的に見れば、漸化式タイプのものが対象ということになるだろう。漸化式を人が解くには、nだけの式に還元しないと手間がかかってしょうがないが、計算機は計算がメチャクチャ速い一方、工夫して解く能力は無いので、ベタで計算してしまおうという話になる。これを実現するのが再帰である。

Forthの再帰 (RECURSE)


多くのプログラミング言語では、現在定義中の関数を、その定義内で呼び出すことを認めている。
これに対して、forthでは、現在定義中のワードの中から、当のワードを呼び出すことは禁止されている。他方で再帰的な関数定義を実現するためRECURSEというワードが定義されている。当の関数を呼び出したい場所に、RECURSEと書くのである。これは、同じ名前のワードを再定義するとき、既存の同名のワードを呼び出し可能にしておけば変更部分だけを追加するだけで済むので便利だから、という判断である。定義中のワードが呼び出せてしまったら、同名の新しい定義の中から古い定義には接近できなくなってしまうので、名前を変えるなど操作しないといけなくなるからである。

以下、簡単なforthのコードは読めるということを前提として、比較的単純な再帰的定義の例を解説し、関数呼び出しが可能な場合との比較を行う。続いて、数学風の漸化式から始めて、それをforthの再帰に解体する方法を示す。さらに、計算機に対する負担が極めて重い再帰を回避して、漸化式をforthのループ計算に落とす方法について述べる。

フィボナッチ数列

フィボナッチ数列は、手前二つの項の和が次の項になるという関係の数列で、初期値は、0ベースにすれば、0,1である。
数列の第n項をf(n)で表せば、

f(n)=f(n-1)+f(n-2)\quad:\quad f(0)=0,f(1)=1

という関係になる。

これを実現するforthワードfibの定義は、次の通りである:
: fib ( n -- n' )   dup 1 > if  1- dup RECURSE swap 1- RECURSE + then  ;

短い。そして、一見、暗号にしか見えず、recurseがcurseに思えてくる(苦笑)。

まず、最後の then は、if文の"括弧閉じ"であって、"条件が成り立つとき"という意味ではないというのはforthの基本である。混乱するという理由で、end-ifに改名して使っている人も多い。
このif括弧は脱出条件を定めている。入力が0のときは0、1のときは1を返すだけで抜けてしまう。それより大きい入力のときだけ中身を実行するのである。再帰的定義には、脱出条件が不可欠であって、これが無いと、理論上は永久に計算が止まらず、実際上はスタックオバーフローでアプリケーションがクラッシュするまで続行される。
なお、ifは判定値をひとつスタックから消費する。

脱出条件を取り除いた内容面を考察する。
 1- dup RECURSE swap 1- RECURSE +
まず、RECURSEは要するに、fibを呼び出すということである。なので、fibと書き換えてみる:
1- dup fib swap 1- fib +
入力をnとしてときのスタックの状態を追ってみよう。
n         \  入力
1-       \ -- (n-1)
dup fib       \ -- (n-1) [(n-1)fib]=fib(n-1)
swap      \ -- fib(n-1) (n-1)
1-        \ -- fib(n-1) (n-2)
fib       \ -- fib(n-1) [(n-2)fib]=fib(n-2)
+         \ -- fib(n-1)+fib(n-2)
と、このように紛れもないフィボナッチ数列の定義である。

ポイントは、ワードfibが1入力1出力のワードであるので、RECURSEのところでトップスタックの入力値一個と結合して、それにfibを適用した出力値に入れ替わる、と考えるところである。後は、スタック操作を工夫するくらいである。

ところで、実はforthでも定義中のワードを定義内で呼び出せるようにもできる。というのも、定義中は名前を検索から隠しているに過ぎないからである。それを露にするだけで呼び出しは可能となる。それをするのがRECURSIVE宣言である。Forth標準ではないが、gforthにあるようだ。iMopsにも定義してある。定義が始まってから、初めにRECURSIVEと書けば、そのワード限りで、定義内からそれ自身を呼び出すことができる。フィボナッチ数列なら、次のようになる。
: fib'  ( n -- n' )  RECURSIVE  dup 1 > if 1- dup fib' swap 1- fib' + then  ;
しかし、あまり分り易くなったとはいえない。forthのように入力をスタックから取る場合は関数の適用は見えにくい。むしろRECURSEと書いた方が再帰に気づき易いように思う。

他方、変数を用いて、パラメターを明示的に書く言語では、定義中の関数と同じ名前で関数呼び出すことで、見やすくなるであろう。しかし、基本的には、言語に関係なく、やることは同じである。まず、脱出条件を、対応する値を返すように書いて、内容は、再帰呼び出しによる計算の結果値をリターンすれば良いわけである。

漸化式のforth-recurse化


まず、漸化式を適当に書いて、それをforthのRECURSEで実装してみる。
ここでは、次の式にしてみる。特に意味はなく、適当に決めた。
f(n)-f(n-1)=2(f(n-2)-3f(n-3))
n-3の項まで関連するので、初期値は3つ必要である。0から始めて順に0,1,2、とでもしておこう。

ワード名はseq1としておこう。まず、脱出条件を書く。
: seq1 ( n -- n' )
  dup 0<= if drop 0 EXIT then
  dup 1 = over 2 = or ?EXIT
 (途中)
入力が0以下のときは、入力を落として0を返して抜ける。EXITというのはこのワードの処理を抜けるワードである。Forthではif-thenの入れ子はコードを読みにくくするとされ、EXITを比較的愛用する。
入力が1か2のときには、そのまま抜ける。overは、ひとつ飛んだ下の値をコピーしてトップに置くワードである。等号条件判定の真偽値を飛び越えて、入力値をコピーするのである。?EXITは、"if EXIT then"の短縮形である。Forth標準規格ではないので定義されていない環境もあるかも知れない。いちいちdupしているのは、条件判定後にも入力値を残すためである。ifも?EXITも、比較演算の結果をひとつ、条件成就のいかんに関わらず消費するので、このプロセスを過ぎた後は、必ず入力値がひとつ、スタックに残っている。

さて、本体にうつろう。
定義式をf(n)=という形に書き換える。単純な移項である。
f(n)=2(f(n-2)-3f(n-3))+f(n-1)
この右辺を実現すれば良い。
右辺は、f(n)を三個含むので、RECURSEも三個必要である。スタック上の掛け算、足し算、引き算をなるべく線形にできるように順序を考えると、まずn-2にfを適用し、次にn-3にfを適用して3倍して、前の値から引いてから2倍、最後にn-1にfを適用して足す、というのが簡単そうである。かくして本体は、
dup 2 - RECURSE over 3 - RECURSE 3 * - 2* swap 1- RECURSE +
となる。意外に簡単!
使用するスタック上の値をいつも上2つぐらいに止めておくと作業が楽である。3つは苦しくなる。4つは厳しい。だいたいforthの標準ワード内で作業しようとすると、そのような感じになる。多過ぎるときは、リターンスタックや局所変数に一時退避させて調整する。

かくして、まとめて定義すれば、
: seq1 ( n -- n' )
  dup 0<= if drop 0 exit then
  dup 1 = over 2 = or ?exit
  dup 2 - recurse over 3 - recurse 3 * - 2* swap 1- recurse +
;
となる。

このワードは3つも再帰しているので、計算機への負担は、入力が大きくなると爆発的に増加する。seq1を試す場合は、入力は30程度までに止めておいた方が無難である(インタープリタが固まってしまう)。

ループへの翻訳


再帰関数は計算効率が悪い。これは、関数の呼び出しが嵩み、スタックフレームが大量に消費されることとか、呼び出しの際のパラメターのsave/restoreのせいでメモリーアクセスが増えること、呼び出しそのものが時間のかかる処理であること、などのような、こともある。しかし、実はそれだけではない。再帰は、後でも述べるが、本当はしなくても良い計算を無駄に何回も繰り返しているのである。そこで、無駄に計算をしない、単純な繰り返しループに書き換えるという考えが出てくる。効率化方法としてよくいわれるテイル・リカースとかテイル・コール最適化という方法は、最後にある呼び出しはリターン手続を省略できるという話のようであり、無駄な計算そのものを減らすという話ではないようである。

問題状況を分解してみよう。
例えば、フィボナッチ数列の場合、再帰は、まず、fib(n-1)を0から計算する。さて次は...?、となって、fib(n-2)といわれると「え〜〜?またかよ!」とばかりに、またfib(n-2)を0から計算し始めるのである。そして、両方が出来上がったところで、改めて足し算をしてfib(n)の値として返す。しかし、fib(n-1)を計算した途中にfib(n-2)は手に入れたはずである。fib(n-2)が分っているなら、fib(n-1)に足すだけで、一回でfib(n)が得られるはずなのだが、コンピュータはfib(n-1)を得た時点で、それ以前のことをキレイサッパリ忘れてしまうのである。おバカにもほどがある!
本当は上の書き方は控えめである。もっと多くの無駄な計算が実施されている。
というのは、上のような0からのやり直しは、各段階で起こっているのである。つまり、f(3)からf(4)を求めるのに、f(2)を0から求め、f(3)に足す;
f(4)からf(5)を求めるのに、f(3)をもう一回0から計算してf(4)に足す;f(5)からf(6)を求めるのに、f(4)をもう一回0から計算してf(5)に足す、
というのである。
そして、「もう一回0から計算して」というのが、そのような各段階がまさに同じように繰り返されるということを意味しているのである!
足し算の計算回数は\Sigma_{k=0}^{n-1}fib(k)になるようである(但し、n=0のときは0回)。効率はO(2^n)規模ということになる(細かくいうとO(1.6^n)くらい?)。

このように考えてみると、計算結果を記憶しておくことが、再帰を回避して、結果にリニアーに到達するための鍵になるのではないかと思われてくる。もしも、再帰関数が、2つ手前までの値に関連するなら、それら2つの結果を保存しておけば足りるであろう。
一般に、漸化式でf(n)が依存するf(n-x)と同じ個数の値を保存しておけば十分である。最後になってから要らないものを捨てれば良い。

そのような考えで、上でRECURSEで実装した漸化式を繰り返しループで実装してみる。あまり創意工夫せず、見え易いようにやってみる。

上の漸化式は、依存項数が3つであるから、値を3つ取っておけば良い。これに入力値を繰り返し回数として加えると4つになるので、上で触れたように、ちょっとスタックアイテム数が多い。そこで、一時退避にリターンスタックを用いることとする。上手く工夫すれば要らないのかも知れないが。
ワード名はseq2としよう。

まず、本体を考える。
初めに、初期値を順に並べて、それに漸化式操作を加え、3つの値が全体として一段階スライドする計算をすればよいわけである。この段階でスタック項目が既に多くなり過ぎるので、リターンスタックを使うが、ともかく、書いてみる。
0 1 2     \ 初期値 -- (n-3) (n-2) (n-1)
rot 3 *   \ (n-2) (n-1) 3(n-3)
>R over   \ (n-2) (n-1) (n-2)
R> - 2*   \ (n-2) (n-1) 2((n-2)-3(n-3))
over + \ (n-2) (n-1) 2((n-2)-3(n-3))+(n-1)=(n)
以上である。
見ての通り、>Rはデータスタックのトップをリターンスタックに移動して隠す。R>は、それをまたデータスタック上に取り出すのである。
2行目からの手続を繰り返し適用すれば、数列はどんどん先にシフトしていく。入力値をむしろ計算繰り返し回数と解釈するわけであるが、3のときに一回処理すれば良いというわけだから、2を引いてループ回数を決めれば良い。この処理の頭に初期値を置くが、forthのループにループ回数を喰わせないといけないので、上で触れたように、ここでもリターンスタックを迂回のために使う。
これらと、計算なしに抜けるための脱出条件に対応する部分を組み合わせると:
: seq2 ( n -- n' )
   dup 0<= if drop 0 exit then
   dup 1 = over 2 = or ?exit
   2 - >r 0 1 2 r> FOR rot 3 * >r over r> - 2* over + NEXT NIP NIP
;
となる。
FOR NEXTはforth標準ではないが、FORがスタックからひとつ値を取って、その回数だけNEXTとの間を繰り返す、簡便なループである。
FORを"0 DO"に、NEXTを"LOOP"に置き換えれば、forth標準で実質同じ内容になる。一番下の行の冒頭で入力値から2を引いてループ回数にし、いったんリターンスタックに隠す。そして、0, 1, 2と初期値をおいた後、リターンスタックから取り出してFOR-NEXTに循環回数として与えるのである。そして、FOR-NEXTに挟まれた、上で述べた数列の前進操作を、必要な回数作用させる。
NIPはforth標準だが、"swap drop"と同値のスタック操作子である。要するに、最後に下の2つの値を落として一番上の必要な項だけ残すのである。

seq2はseq1と比べると劇的に速い。
seq1に40を入力したときは、計算が終わらなくて、待ち切れずiMops強制終了してしまったが、seq2なら50程度でも一瞬である。(ちなみに、40前後でもう4バイト数を越えている。)
このアルゴリズムの効率は、明らかにO(n)である。
この数列は、適当に作ったわりには挙動が面白く、5個毎に符号を替えながら、次第に振幅を拡大していく。拡大するギザギザグラフである。
手で計算してみたけど、10番目でもう間違えたよ。あー。

ちなみに、同じ発想でフィボナッチ数列のワードも書いてみれば良い。
一応、ひとつの例をfib2として挙げておく:
: fib2  ( n -- n' )   dup 1 > if 1- 0 1 rot FOR swap over + NEXT nip then  ;
これも入力値がある程度大きくても極めて速い。

教訓:
最適化コンパイラによる高速化は、せいぜい数倍、多くは数十パーセント止まりだが、アルゴリズム改良による高速化は、数十倍、ときには100倍以上にもなる。

再帰的処理一般


とはいえ、再帰的処理は漸化式計算に限るわけではない。例えば、Mopsにおいては、多重継承クラスが可能である。そのインスタンスを初期化する際、継承関係のツリー構造を遡って、枝の先(葉)— つまり最上位クラス(むしろ根と考えるのが普通だが) — から順に当クラスの初期化メソッドを実行しなければならないが、そのために再帰的処理を用いている。しかし、そこではワードRECURSEは使っていないDEFER(MopsではFORWARD)の機構を用いて、互いに呼び出し合う2つのワードによって再帰が実現されている。

このように、あらかじめ構造が確定していない構造木の結節点全てについて処理しようとするような場合には、再帰的処理がもっとも簡単である。そしてこの場合には無駄な処理があるわけではない。再帰処理そのものが「おバカ」なのではない。最適な使用場面もあるのである。「一つ覚え」的な使い方が「おバカ」を招く、と。

iMopsでの多重継承クラスインスタンスの初期化のアルゴリズムについて、ひとつの例として簡単に説明しておこう。継承ツリーの根元から始める。

: word1
  1. 分枝のリストをチェック、空ならば脱出する
  2. リストから取り出された枝データにword2を適用
  3. 適用後の枝を切り落とし、1に戻る
:word2
  1. 渡された枝をひとつ遡り、word1を適用
  2. 現在の位置の処理(初期化メソッド)を適用

以上である(実際は、インスタンス変数の初期化があるので、もう少し込み入っているが)。

RECURSEを用いた上の計算と考え合わせると、再帰(Recursion)はツリー構造と密接に関わるものであることがわかる。ツリー構造の総当たり手続、といった感じである。もっとも、それもループでできないことはない。しかしそうすると、上で初期化メソッド適用後に前の分岐点に退却するためのデータを保存しておく必要がある。実行速度やコードの書きやすさ、などの比較で決めれば良い。上の例の場合は、初めはループで書いたが、再帰の方がコードが簡単になった。
 ここでも、再帰をループに書き換えるポイントは"記憶"である!けれども、ツリー探索の場合、再帰による"自動的記録"が役に立っている。





最終更新:2015年07月21日 11:54