再帰(Recursion)というのは、言ってみれば汎用アルゴリズムの一種で、
ループとか
条件構造と似たようなものです。何か特定の問題をうまく解くために開発された方法というわけじゃなくて、そういうやり方を使えばコードが明快になる場合がある、という感じですか。ただ、ループや
条件構造よりも、少し論理的に込み入っているので、まあ、話としてはちょっと後にでてくるわけです。で、その実現(実装)の仕方についても、ちょっと入り組んだ話があるんで、その話もちょっと触れときます。これも少し長くなりそうな気配(^^;;)。
その理屈
本質的には
ループと大して変わらなくって、定型的処理を必要な回数だけ繰り返して適用するのが、再帰です。再帰定理というのがあって、再帰と
ループは機能的に違いがないことが証明されているそうです。つまり、原理的には再帰で書けるコードは
ループで書けるんだそうで、じゃあ再帰なんてなくてもいいじゃんって話なわけですが、再帰の方がソースコードの意図が明瞭で簡単になる場合もあるってのが、その存在理由とされています。っていうか、Scheme(LISP系の関数型プログラミング言語)とかだと、繰り返し適用は
ループじゃなくて再帰を使うんだそうです。再帰を
ループよりも基本的としている言語から見れば、原理的には
ループは再帰で書ける、と、同じ再帰定理でも逆に読むんですね。
話によると、再帰の理屈が理解できるかどうかが、最初の躓きの石なんだそうですね、プログラミング入門では。まあ、学校で習ったことのない私にはホントにところは解りませんが、なんで「躓く」のかというと、多分、まだ定義中のものを定義の中で呼び出すからじゃないでしょうかね。以前、タイプに関連してちょっと触れたラッセルのパラドクスの出発点の話みたいな感じがするんじゃないでしょうか。不確定なものを利用していいのか、と。ホントは
ループと同じようにちょっと前に戻るだけなんですが、
ループには普通、はじめと終わりを標す括弧構造がありますからね。再帰には普通ないです。というか、再帰は、ひとつのワード(関数)という括弧構造を途中で分断してしまいます。初めは、順番に再帰より前の部分をぐるぐる回していって、抜けたところで、今度は再帰より後ろの部分を逆順にぐるぐる巻き戻す、というイメージです。
自分自身の中で自分自身を呼び出してたら、「合わせ鏡に映る私」みたいで際限がない感じがしますよね。でも、脱出口があるんですよ、再帰には、必ず。
ループだって、それを抜けるポイントつくるのを忘れたり、脱出の条件が実は絶対に成就しない条件だったりすると、無限ループに入って大変な目にあったりしますよね。同じことです。ただ、ループの場合、処理が終わったよ、ってんで繰り返しを脱出しますが、再帰の場合、脱出条件が整ったところで初めて作業が開始される場合があるという違いがあります。投網かなんかを、ビヨーンと投げて、遠くに落ちたところで、ザザザざーっと引き寄せて魚を捕る、みたいな感じですかね。投網が一番遠くに達した点が、ここでいう「再帰の脱出口」に当たります。あるいは、昔よくあった、蛇腹みたいになってて、びょーんと伸びるマジックハンドで何か取る感じ、ですか。いやあれは縮むときにはモノを放しちゃうんでだめですね。最近は、何か特殊ゴムみたいのでできてて、びょんと伸びて、先にあったものをくっつけて取るという「カメレオンの舌」みたいなのがあるようですね。
いや、まあ、こんなイメージの話ばかりしててもしょうがないですね。「脱出口」というのは、ある条件下では自分自身をもう呼び出さない、というコードです。これはぜひとも必要になります。それと、繰り返し適用されるべき処理の本体、これを記述するコードもやはり必要になります。この本体部分は自分自身の呼び出しを含んでいていいことになります、というか、普通、含んでいます。一歩手前で自分自身を適用した結果を利用するのが、再帰の特徴ですから。この処理が、脱出口に達したところから、再帰呼出し自体のあとに書かれた処理が、だだだーっと、入れ子状に適用されていって、最終的に必要な結果を得ることになるのです。
Mops/Forthでの再帰
Mops/Forthでは、自分自身を呼び出すポイントに、"RECURSE"というワードを書くことになっています。他の言語では、SchemeでもCでもそのようですが、普通は、その関数の名前で呼び出すことになっているようです。Mops/Forthでは、既定義の同じ名前のワードを呼び出して少し変更したワードでオーバーライドできるようにするため、現在定義中のワードの名前は、意図的に隠しています。その代わり、コレは再帰ですよ、ということを明示するためにRECURSEというワードを準備したわけです。
階乗計算
簡単な例で説明しましょう。階乗計算をしてみましょう。5の階乗は1×2×3×4×5ということですよ、念のため。
: Factorial ( u -- u! )
dup 0<= IF drop 1 EXIT THEN
dup 1- RECURSE * ;
かなり限定的なものですが、簡単なところで。階乗はすぐにでかくなるので、4バイト数だと、13くらいでもう溢れちゃうでしょう。上のコードの"EXIT"というのは、もうこのワードは抜けます、というワードです。これは使わないでも同じ働きをするコードは書けて、
: Factorial' ( u -- u! )
dup 0<=
IF
drop 1
ELSE
dup 1- recurse *
THEN
;
となりますが、生成されるマシンコードは、多分、EXITを使った方が少し小さいと思います(あやふや)。後の方が、構造は分かりやすいかもしれませんね。つまり、このワード"Factorial"脱出口は、入力値が0以下となったところです。そのときには、入力値を捨てて、代わりに1を出力します。
もっと大きい入力のときはどうするかというと、入力値を複製し、一方を1減らします。そして、その減らした方の値を入力値としてRECURSEするわけです。つまり、その定義中のワードを呼び出します。そして、その出力をもとの入力とかけ算するのです。これが階乗計算の全貌です。
数学が得意な人なら、関数式で書くと一目瞭然でしょう。Factorialは、次のような漸化式で定義されているのです。
Factorial(0) := 1
Factorial(n) := n × Factorial(n-1) (nは自然数)
Forthワードの定義との対応関係も分かりますよね。もうコレで、数列とかの漸化式が与えられたら、すぐにForthで書き下せますよね .... ってことはないかな、ヤッパリ(^^;;)。
基本は、本体関数を呼び出したいところにRECURSEと書く、ということになります。上のFactorialでは、
f(n):=n*f(n-1)
なので、逆ポーランド式で書けば、
(n)f := n (n-1)f *
なわけで、本体関数自体は、nをスタック入力として取ることを予定していて、定義内容も、スタック上にnが一つあることを想定して書きます。スタックの状態を
コメントしていくと、
: f \ -- n
dup \ -- n n
1- \ -- n n-1
f \ -- n (n-1)f
* \ n (n-1)f *
;
となるわけです。定義内で呼び出されたfをRECURSEに置き換えて、
; f dup 1- RECURSE * ;
これは、脱出条件を省いた本体の定義になってますね。
フィボナッチ数列
じゃあ、簡単なのをもう一個。他のページでも扱いましたけれども、いわゆる、フィボナッチ(Fibonacci)数列です。これは、一個前の項との比が、黄金分割比に近づいていくってことでも有名ですね。漸化式からコードを書いてみましょう。"Fibonacci"って名前のワードにでもしましょうか。定義は、
Fibonacci(0) := 0
Fibonacci(1) := 1
Fibobacci(n) := Fibonaci(n-1) + Fibonacci(n-2) -- nは2以上の自然数
でいきましょう。型通り翻訳してみます。まず、脱出条件です。
: Fibonacci ( u -- u' )
dup 1 <= IF 0 max EXIT THEN
...
まあ、間違って負の数を入力する人のためちょっと誤摩化します。0と比べて大きい方の数値をとるというのが"0 max"です。0,1なら、それぞれ適当な出力がでることが分かりますよね。ここは脱出口なので、あとはEXITです。それから、本体ですね。ウンと改行して書きましょうかねえ。
... \ -- n
1- \ -- n-1
dup 1- \ -- n-1, n-2
RECURSE \ -- n-1, (n-2)RECURSE=Fibonacci(n-2)
swap \ -- Fibonacci(n-2), n-1
RECURSE \ -- Fibonacci(n-2), (n-1)RECURSE=Fibonacci(n-1)
+ \ -- Fibonacci(n-2)+Fibonacci(n-1)
;
おしまいです。対応関係はわかりますね。合わせて普通に書くと、
: Fibonacci ( u -- u' )
dup 1 >= IF 0 max EXIT THEN
1- dup 1- RECURSE swap RECURSE + ;
コードは短い。観念的にも明快なので翻訳も簡単。ところが、このワードは絶望的に遅いのです。その理由は計算をいっぱい無駄に重複してするからなんです。概念的に簡潔で明快だが、そのままだと効率が悪い、というのが再帰の特徴ともいえます。再帰の効率の話は後で説明することにします。フィボナッチ数列なんかは、
ループで書く方がずっと速くて、コードもそんなに難しくありません。というわけで
ループで書いてみると、
: Fibonaci2 ( u -- u' )
dup 1 <= IF 0 max EXIT THEN
0 1 rot 1- FOR swap over + NEXT nip ;
データスタックが少しごたごたしていて、コンパイルされるマシンコードも後者の方が長い程なんですけど、無駄に再計算したりしないので、圧倒的に速くなります。まあ、気が向いたら、RECURSE版と
ループ版とを、入力40くらいで比べてみてください。うちの機械ではRECURSE版は一瞬壊れたのかと不安になります(^^;;)。入力値があまり大きいと、これも1セルをはみ出しちゃいますので注意。
再帰は特に数理論理学では基本的な概念です。その意味では、アルゴリズムと相性がいいんでしょうね。これは基本的に帰納関数とか再帰関数(recursive function)という話に連なるものといえるでしょうね。Recursiveが「帰納」と訳されてるんですが、どうなんですかね。論理的な意味での帰納(個々のものについて成り立つことから普遍的に成り立つことを引き出す)とは意味合いは違います。帰納はinductionですが、いわゆる数学的帰納法ってのが、mathematical inductionというんですが、これもその実体はrecursiveな証明なんですね(^^;;)。まあ、数学ではrecursionのことをinducutionともいうのだと思えばいいでしょう。
帰納関数というのは、計算可能な、つまり有限の手順で結果が出せる処理、ということで、計算可能性の理論と密接な関連があるようです。でも、コンピュータプログラミングの仕組みとしてのRecursionと特別に結びつけるのはどうなんでしょうかね。というのは、帰納関数というのは、むしろ、特殊な関数というより、計算可能なアルゴリズム全般のことなんですよ。帰納関数なら計算できる、というのは分かっている。計算可能なら帰納関数か？そうだ、と主張するのがチャーチ(Church)のテーゼですね。でも証明できない。反例もないってことは、普通の計算はみな帰納関数なんですよ。足し算も。まあ、漸化式で書けるようなものは計算できるってわかってるんだから帰納関数であるということはそうなんでしょうけど、特に再帰のときだけ関連性を云々する意味はあまりないんじゃないですかね。
ちなみに、帰納関数とはどういう関数か、っていうことの定義も帰納的(recursive ^^;;)ですね。まあ、これは、計算可能性を重視する観点(Constructivism)からは全く自然なんですけどね。計算できる関数の有限個の合成として表現できるもの、ってかんじですか。五千八百兆回の計算で実現できる、ってのが本当に現実的に計算可能かってのは、この際、気にしないんですね(^^;;)。
多分、帰納関数のrecursiveは、ある有限アルゴリスムで得た結果に、また重ねてアルゴリズムを適用していくことを有限の範囲で認める、というところに注目しての命名と推測されます(多分、定義の仕方がrecursiveだからではないと思います)。コンピュータのRecurseも「重ねて適用する」というか「再施」という感じが共通ですけどね。要は一種の関数の合成なわけですが。気分は同じなんですかね。
再帰と効率
再帰はそのままやると、効率がよくありません。メモリー消費もバカにならない、といわれることもあります。どういうことなのでしょうか。
再帰は、ストレートに実装すると、現在定義中の関数(ワード)をそこで呼び出すという形式になります。問題は、その関数の呼び出しのときにどういうことが普通おこなわれているのかです。大抵の場合、入れ子になった呼び出しのときは、その呼び出しの都度、スタックに値を積んでいくようになっているのです。Forth系でいうと、いわゆるリターンスタックです。つまり、戻る地点のアドレスをメモリーに保存しておくんですね。それと、C言語系だと、帰るときにもとに戻しておかないといけないレジスタも保存します。さらに、局所変数もいっぱい使いますが、外に出て帰ってきたときに(呼び出しがリターンしてきたとき)局所変数の値が分からなくなっては困るので、呼び出しのときは、それらも保存します。関数への引数の現在値も呼出し前に保存しておかなければなりません。あれやこれや、C言語系では結構呼び出しには保存すべきものが多いんですね(値の状態をまとめて、"コンテクスト"とかいうようです。)。C言語系では各関数がスタックフレームと呼ばれるメモリー枠を確保して、そこに保存します。各関数は大抵自分専用のスタックフレームを確保します。そのフレームを関数呼出しの度毎に、まさにスタックのように積んでいくんですね。そのような各関数毎のスタックフレームはかなり大きくなる傾向にあります。それに入れ子の呼出しが嵩めば、スタックフレームはどんどん積もっていきます。例えば、ひとつの関数が20セル分(現実と比べるとかなり小さめではないかと思いますが)のスタックフレームを確保したとして、100回再帰すれば、総計2000セル分のスタックフレームが必要になるわけです。これに対して、
ループは、ひとつの関数内で、実行箇所をちょっと前に戻すだけで済みます。いちいち、戻る毎にスタックを準備する必要がない。これが、「再帰はスタック(メモリ)を消費する」といわれていることの中身です。
まあ、メモリーが希少だった頃はメモリー効率の意味は大きかったんでしょうが、今では、アプリケーションレベルの話としてはそれほどともいえません(埋め込みとかだと、まだ問題になる)。ところが、再帰は、計算速度も遅くなるのです。というのは、再帰の度毎にメモリーに沢山の値を保存するわけです。以前の回で触れましたが、メモリーへのアクセスというのは、CPU内部での計算と比べて概して遅いわけです。呼び出しから戻るときには、レジスタを原状回復して戻すわけで、一旦保存された値は、この度はまた読み出されなければなりません。10アイテム分で10回の回帰だと、行きに100アイテム分の保存、帰りにまた100アイテム分の読み出し。たった10アイテムで10回の呼出しなのに、それだけのために200回という大量のメモリーアクセスをおこなうことになるわけです。
しかし、本当は、これは特に再帰だけの問題ではありません。関数(サブルーチン)の呼び出しそのものが、結構負担が大きいものなのです。再帰は、それをたくさんすることになる、というに過ぎません。この超過負担のため、C言語などでは、関数をできるだけ大きくして、他の関数の呼び出しを最小限に抑える方が、少なくとも実行速度の点では有利になっているのです。ただ、あまりにも長い関数を定義すると、何をやっているのか辿るのが大変になります。つまり、コードの保守性が落ちるというわけです。モジュラーなコードも書けなくなります。コンパイラがうまくやってくれることが多くなったそうですが、それでも、この実行速度と保守可能性のせめぎ合いは、速さが必要なコードでは、今でも大きな問題らしいです。
ここまで、C言語、C言語と言ってきたことにもお気づきでしょう。ここで言っている超過負担の問題は、よく考えてみると、関数、もっと広義の呼び名ではサブルーチンの呼び出しのときの仕組みがそうなっているからでてくるものだということに気付くでしょう。C言語では、標準的に、上のようなスタックフレームを作って、関数呼び出し時にたくさんのアイテムをそこに保存するという仕組みが採用されています。多くのコンピュータもそのような使い方をすることを前提につくられています。でも、そうしなきゃいけないってものではありません。別のやり方もありうるのです。ですが、そうはいっても、局所変数を使わない言語というのは、現在ではほとんどありません。呼び出しの前後で維持しておきたい局所変数は、その関数専用のスタックフレームを作ってどこかスレームに保存しておき、用がなくなったらフーレムメモリー領域ごと解放する、というのが一番効率がいいのです。そんなこんなで、スタックフレームを積む、というのが標準的なサブルーチンコールの方式なわけです(歴史的には逆かもしれませんが)。また、計算処理には遅いメモリーよりも、レジスタで計算したいため、レジスタの個数がいきおい増えてきています。いわゆるRISCと呼ばれるタイプのCPU(PowerPCもそれに含まれる)では、レジスタの個数はかなり多くなっています。値をメモリーにあるまま操作することはできず、必ずいったんレジスタに読み出すことになっているからです。サブルーチン呼び出しの前後で値を変えてはいけないレジスタというのも相当個数に上ります。かつてのMacで使われたPowerPCのCPUだと、大体、整数用と小数用、それぞれ20本ずつくらいが、値を変えてはいけないレジスタです。つまり、それらを使う場合には、いったんその値をメモリーに保存して、使った後は元に戻して返してやる必要があります。ちなみに、PPC Macintoshでは、これらのレジスタは局所変数のために使うとされています。レジスタでおさまりきれない局所変数は、メモリーを直接使います。結局、サブルーチン呼出しのときに必要になるメモリーアクセスの主要部分は、局所変数を使うために必要となる保存／回復操作であるということになります。
それなら、局所変数を使わないなら負担は軽くなるのか。実際その通りなのです。局所変数を使わない言語、といえば、もちろん、Forth系はまさにそうです。確かに、コードの行き先の方向転換をするだけでも、一本調子で実行が先に進むのと比べると平均的にはいくらかのロスはあります。それは
ループも同じことで、その点を更に最適化しようという話もあります。ですがその話は別とすると、Forth系は呼び出しの超過負担が非常に小さいことが特徴となっています。Mopsの場合も、局所変数を使えば使った分だけレジスタの保存/回復作業を必要としますが、それなしでやれば、呼び出されるワードへの入力のための
データスタックと、戻るところを記録しておくリターンスタックアイテム一個分(ただし、2セル(64ビット)になっている)だけしか、メモリーとの遣り取りはありません。重複して保存されるアイテムというのもなく、必要最小限となっています。ですから、Mopsでは再帰の非効率がこの局面で問題になることはないと考えて良いと思います。ただ、このように、Mopsではもともと再帰があまり非効率的ではないせいか、あまり頑張って最適化しようとはしていません。後に述べるようなTail-Recurse最適化もないようです。いずれにせよ、その言語のサブルーチン呼び出しの仕組みが大きくかかわっているのです。Mopsは再帰それ自体は遅いわけではない言語ということになります。
再帰呼び出しの最適化
レジスターや、その他アイテムを保存-回復するための超過負担を軽減する簡単な最適化方法があります。LISPやSchemeなど、再帰を繰り返し適用の基本としている言語では、このような最適化は仕様として要請されてさえいるようです。いわゆる、末尾再帰最適化(tail-recursiton optimization)です。(訂正：LISPは末尾再帰最適化を仕様として要求するわけではないようです。言語仕様を見たわけではないので、あやふやですみません。Schemeでは仕様のようです。いずれにせよ、関数型言語は、再帰を繰り返し適用の基本形としているのは間違いないようです。
ループの機構が無いわけではないらしいですが。)
実際には、これは再帰の最適化というより、サブルーチン呼び出し一般の最適化方法で、もっと広い意味では、tail-call optimizationと呼ばれています。末尾呼出し最適化、ですかね。
ただ、この最適化方法は、特定の局面でしか利用できません。その名が示す通り、[再帰]呼出しが、呼出しがわの末尾にある場合に限ってできるやり方なのです。末尾にある、とはつまり、呼出しがわの実体処理はもう終わっているので、呼び出した処理が終わって自分に処理が戻ってきた後は何もすることが残っていないという状態です。この状態で再帰呼出しをするように注意すれば、最適化が適用できて超過負担を軽減することができる、というわけです。
具体的には、まず、呼出し側には処理が残っていないのですから、そこで使われる局所変数は、もう呼出し前に保存しておく必要がありません。さらに、再帰で10段階呼び出しているとして、10番目が終わったら9番目に戻るわけですが、9番目に残っている処理は、8番目に戻る、ということだけです。なので、もう10番目から全部すっ飛ばして、一番最初に一気に戻ってしまえるわけです。で、一番最初(再帰を含んでいる関数)が呼び出されたときの状態を回復して振り出しに戻してやれば完璧です。で、再帰としてこの状況をもう一度考えると、保存するものもない、よって回復するものもない、自分自身の呼出しなんだから、出かけるのも自分自身の頭、戻ってくるところも自分自身のお尻と決まっているわけで、いちいち、お出かけの形を取る必要はないわけです。つまり、もともと、再帰するのにリターンアドレスの保存さえ不要なわけです。スタックフレームなどつくらず、普通に実行を頭に戻すだけのコードで書けるのです。再帰をこのような実行コードとしてコンパイル(ないし解釈)することを末尾再帰最適化というわけです。このようなことができるなら、再帰呼出しの特有の超過負担はほとんどなくなってしまうわけです。
用語法補遺：ちょっと、言葉の使い方について補足します。上で、末尾再帰最適化のことを大雑把に説明しました。再帰を用いているコードが末尾再帰になっているかどうかは型通りのチェックでわかりますし、型通りに単純な分岐ループ(頭に戻るGotoみたいなもの)に変形できるわけで、多くのコンパイラはこの最適化を自動的に行うようです。特に上にも書きましたがSchemeでは言語仕様として最適化が要求されていると聞いたことがあります。そのせいか、最適化されている末尾再帰という意味で、単に「末尾再帰」という言い方もときどき見かけます。なので、「末尾再帰」と聞いたら、言葉通り末尾で再帰をしているコードだという意味で言っているのか、最適化された再帰(つまり、効率が悪くない再帰)コードという意味で言っているのか、用心する必要があるようです。
Fibonacciはなぜ遅かったのか
Mopsは再帰の超過負担が小さい、といいました。なのに、"Fibonacci"は、なぜ絶望的に遅かったのか。これは呼出し云々というより、再帰そのものの実装の問題なのです。前にもいいましたが、そのままでは無駄な計算が多すぎるのです。再帰の観念そのものには問題はないと私は思います。実現手順の問題です。いってみれば、その直前までに得た情報のほぼ半分を捨ててしまって、はじめから再計算しているのです。例えば、Fibonacci(5)を得るために、Fibonacci(4)とFibonacci(3)を得て、それを足し合わせたとします。じゃあ、次にFibonacci(6)に移ろうとしたときには、今得られたFibonacci(5)に、前にもう計算してあったFibonacci(4)を足せばいいわけじゃないですか。少なくとも、再帰関数の概念ではそういうものだと私は思います。ところが、上の二重のRECURSEを使ったコードでは、Fibonacci(5)は使いますが、Fibonacci(4)は0からまた再計算しているのです。七項目を得るときには、五項目は0から再計算、八項目を得るときには、六項目は再計算、、、という具合で、しかも各再計算の中身も、そこまで上がってくるまでに再計算のオンパレードです。それで、項目40ともなると、もうものすごい計算量なのです。ぼんやり考えると、計算の規模は2nよりちょっと小さいくらいですかね。計算自体がフィボナッチ数列みたいに増えていくんで、もしかして黄金分割比(1.6ちょっと)のn乗規模なんでしょうか --- 計算方法知らない(追加：おまけ付けました)。小さいnだと計算自体がフィボナッチ数列+1で増えていく感じなんで、40項目を計算するには初めの項のだいたい二億倍以上の時間がかかる感じです(^^;;)。
だいたいのイメージですが、関数"fibo(n)"と短くして-- そうしないと字がかぶっちゃう(^^;;) -- 、fibo(6)でどれくらい計算するかを図に書いてみました。二つの矢印が交わるところでひとつ足し算です。これを全部するんですよ。そいでもって、fibo(7)に上がるときは、左側のfibo(5)を頂点とした一房の部分を右側にもう一個くっつけて、それと、fibo(6)と足してfibo(7)です。かなり計算がダブってることが分かると思います。でかい絵ですみません(でも、結構、描くの大変だったんですよ、ええ。)。
比較のために、
ループで計算するときの手順は次のような感じです。
上の足し算12個に対して、こっちは5個です。fibo(7)を計算するには、上ではあと8回足し算が増えますが、こっちはあと1個増えるだけです。
ここは、おまけ
そんなわけで、再帰自体が悪いわけではない、ってことで再帰の再起を賭けて、再帰を使った速いフィボナッチを書いてみました。
: Fib-Recurse ( u1 u2 #itm -- res )
dup >R 0= IF nip R> drop EXIT THEN
swap over + R> 1- RECURSE ;
: Fibonacci3 ( #itm -- res )
dup 0<= IF 0 max EXIT THEN
0 1 rot Fib-Recurse ;
って、よーく見ると分かっちゃうんですが、実はこれは再帰のふりして実体は
ループなんですね。
ループのコードの
ループ部分を再帰で書いただけなんですよ、実は。それでも、"Fib-Recurse"はまぎれもなく再帰を使ったコードですよねえ。こうするだけで速いんですよ。再帰は使い方を工夫しろ、ということでしょうね。
フィボナッチついでに、もっと大きい数も出せるやつを書いておきましょう。Mopsにはdoubleというライブラリファイルがついています。これは、小数の方じゃなくて、2セル整数を扱うためのライブラリです。これをつかって、64ビット数まで結果をだせるFibonacciを定義してみます。
ループの方を使いますね。
まずPowerMops上で、
// double<enter>
として、doubleファイルをロードしてください。それから、ワードを定義しますが、名前は、まあ、"Fibonaccid"とでもしときます。
: Fibonaccid ( u -- ud )
dup 0<= IF 0 max s>d EXIT THEN
>R 0 s>d 1 s>d R> FOR 2swap 2over d+ NEXT 2swap 2drop
;
これで、93項までは大丈夫です。計算は一瞬です。ただ、残される結果がダブル形式でよくわからないかもしれないので、終わった後に、
ud.<enter>
としてみてください。負号なし64ビットだと完全に使い切れる桁は10進では19桁分だけですね。1.8446×1019程度を超えると溢れます。Schemeとかみたいに64ビット数を超える巨大数値計算のサポートは、いまのところないです(おそらく)。自分でライブラリを書く必要があります(多分)。
上で、再帰による遅くないFibonacci数列のコードを書きましたが、この中で再帰を含んでいるワード"Fib-Recurse"は奇しくも(?)末尾再帰になっています。PowerMopsでは別段これを分岐としてコンパイルするような最適化は働きませんが、それでも、十分速いものになっています。末尾再帰というのは要するに、再帰した結果に何らかの処理を加える必要がないような書き方をするということです。再帰を基本とするプログラミング言語では、できるだけ末尾再帰に持ち込めるように書け、といわれます。でも、それって、結局、
ループで書くってことなんじゃないかという気がします。再帰のイメージとしては、まず初期条件が与えられていて、そこに至るまで準備していって、到達した地点からパタパタと計算して最終結果を得る、という感じだったんですが、末尾再帰というのは、抜けたときには全部終わってるんで、結局、初めから計算してるんですね。それは、
ループのイメージに近い気がするわけです。ま、上のコードは、まさに
ループのコードを翻訳したんですけどね(^^;;)。
ストレートに再帰を適用した場合、具体的計算を留保しつつも第n項めから始めていって、端に至って最終的計算を開始する、という感じなんですが、上のようなコードの場合、実はいきなり初めの項から計算を始めてる。そして、再帰呼出しした自分自身にパラメターとして与えているのは、実は、残り項数なんですね。それ、まったく
ループのインデックスじゃないですか。
ループのインデックスの値が破壊的に変更されるのがよくない、とか関数型言語ではいうわけで、それが再帰を好む一因となっているわけですが、う～んというかんじですねえ。関数への入力だから、その都度違っていいのか、そういうことか？ええっ？詭弁(イイノガレ)じゃねえのか？(^^;;)なら、MopsのFOR-NEXT
ループ版だって、
ループのインデックスは使ってないぞ(使えるけど^^;;)。何か別のやり方もあるんでしょうかねえ。まあ、よくわかりません。
最終更新：2019年09月21日 09:31
