フィボナッチ数列と継続受け渡し方式と末尾再帰

前回、Pythonでちょっと変わった実装をしたフィボナッチ数列のコードを見せた。

def fibs(n):
　head = [0, 1]
　if n < 2:
　　return head[:n + 1]
　else:
　　tail = fibs(n-1)
　　return head + [sum(i) for i in zip(tail[:-1], tail[1:])]

これはこれで良いのだが、実は実行効率がちと悪い。

再帰が嫌われる一つの理由が「実行効率が悪い」と言う事が挙げられる。

なんせ関数Aを実行してる途中で(事実上)別の関数Aを呼び出し、そしてそいつがまた別の関数Aを呼び出し・・・とやってると一番内側の関数の処理が終わらないと大元の関数の処理がいつまでたっても終わらないのだ。

つまり処理は「待て」って言われるわけだな。

実は単純なモデルだと、コンピュータではプログラミング言語上で作った「関数」はスタックと呼ばれるメモリ領域に保存される。そうすると「待て」と言われた状態で別の関数を呼び出すとまたスタックが消費され、そいつがまた別の関数を呼び出すとまたスタックが消費され・・・と一番内側の関数の処理が終わらない限りスタックが消費され続け、下手すればスタックがパンパンになってしまう。

スタックが満杯になってスタック領域より別のメモリを使おう、と言う状態になるのが、いわゆるスタックオーバーフローである。「深刻なエラーを」生じるわけだな。

まぁ、今現在のようにメモリが潤沢にあると、再帰を使うのはそこまで心配せんでもいいのだが、90年代くらいまでの非力な・・・と言うかMbクラスのメモリしか使えないような時代だと、この辺で深刻でクリティカルな問題を発生する頻度が高かったわけだ。

そんな理由で、数学的な美しさに関わらず、今でもある種、往年のトラウマのせいで、再帰が嫌われているわけである。

ところで再帰には二種類ある。一つは通常の再帰、もう一つは「末尾再帰」と言われる形式だ。

末尾再帰とは何か?

Wikipediaには次のような説明がなされている。

末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出しという。

ちょっと抽象的だろうから実例を見せる。

階乗を計算するPythonの再帰コードを二種類見せよう。

# 非末尾再帰
def fact(n):
　if n == 0:
　　return 1
　else:
　　return fact(n - 1) * n

このコードの末尾呼び出しは、字面通りに解釈するとreturn fact(n - 1) * nで、ここでfact(n-1)とnの積を求めている。

言い換えると本体の関数fact以外にも計算が必要で、* nがあるため再帰部分が終了しないとこの部分はreturnされない。

returnと言うのは以前書いた事があるが、関数を呼び出した側に制御を「戻す」と言うのを意図している。上のスタックの例で言うと、関数を呼び出して計算が終わった時点で、情報を得てスタック上のその関数を破棄して良い、って事になるはずだが、上の形式だと長い時間スタック上のあるメモリを専有し続け、最内の計算が終了したあと、値が返されまくって外側の大元に戻るまでスタックに居座り続けるのである。

我々が欲しいのはたとえ再帰だとしても、理論上、表層の計算が終われば即刻スタックを破棄してくれるような再帰の書き方であり、それが末尾再帰なのである。

# 末尾再帰
def fact(n, r = 1):
　if n == 0:
　　return r
　else:
　　return fact(n - 1, n * r)

これが末尾再帰である。末尾呼び出しの部分が元々の大枠のfact以外を呼び出していない。大元の関数以外を呼び出さない、それが末尾再帰である。

理屈から言うとreturn fact(n - 1, n * r)の時点でfact(n)は消滅して構わない。大元の関数の役目はそこで終わるので、計算結果の情報 n * rを(第二)引数としてfact(n - 1, 第二引数)に受け渡してあとは消えて構わないのだ。

実はここで書いてる事はあくまで理想論なのだが、いずれにせよ、スタックに対する「負担」は末尾再帰の方が遥かに少ない、と言う事が感覚的に予想出来るだろう。

また、上のコードを見てみると、末尾再帰の大きな特徴が分かる。それは計算は関数本体と言うより引数内で行われている、と言う事だ。

上のPythonによる末尾再帰は引数が一つ増えている。rと書かれたヤツがそれで、このような計算結果を詰め込む引数を通称アキュムレータ(累積器)と呼ぶ。計算はここで行われてて、末尾再帰は大体のケースでは本体では粛々と本体だけを呼び出すだけ、の形式になってるモノが多い。

ついでに理論的な話をする。原則、どんな再帰でも末尾再帰に変換が可能だ。・・・言語のパワーにも拠るけどね。必要なのはラムダ式である。

形式的な話をするとラムダ式さえあればどんな再帰でも末尾再帰に変換が可能である。

言い換えるとC言語だと無理なケースがある。

Cだと可能な場合もあるし不可能な場合もある。

そういう事だ。

いずれにせよ、再帰も末尾再帰もすぐさま書けるように練習しておくことが大事である。ただし、上のフィボナッチ数列のコードのように一体どうすれば末尾再帰に変換出来るのか、一発で分からない場合もあるだろう。そこで、ここでは再帰は分かるけど末尾再帰がピンと来ない人の為に末尾再帰への形式的な変換の手法を説明する。

なお、通常の言語・・・引数が最初に評価される、「先行評価」と言われる言語だと一般に末尾再帰が有利なのだが、一方、Haskellのような「遅延評価」前提の言語・・・最初に関数部分が評価され、必要に応じて引数が評価されるタイプの言語だと末尾再帰はあまり有効な手段ではない。ないどころか無限ループに陥ったりややこしい事になったりするのだ(笑)。

従って、遅延評価前提の言語ではフツーの再帰を使った方が安全だ、と言う事は言っておく。元々「遅延評価」と言う名前が表してる通り、「待て」ってのを前提に作られてるプログラミング言語だとフツーの再帰の方を難なく処理するように設計されてるので、末尾再帰のようなテクニカルな事をすべきじゃない、とは言える。

1. 継続受け渡し方式

ここでは継続受け渡し方式(Continuation Passing Style)と言う手法、略してCPSと呼ばれるが、を用いて上のフィボナッチ数列のコードを末尾再帰に直す。これはラムダ式が使える言語だったら必ず、と言って良い程使える方法論である。

以前別のトコでも書いたが、継続、と言うのは単に計算途中の情報を別の関数に受け渡してる状況の事を指す。ピンとこないかもしれないけれども、実は大した事は言ってない。

単にまずは、

def fibs(n, cont):

で書きはじめるだけ、だ。

これでfibsで計算した情報がcontに受け渡される・・・え、引数って受け取る為のシステムであって、受け渡す対象としてのモノじゃないんじゃないの?と軽く混乱するかもしれないけど、大丈夫。実は大した事はやってない。

ここでcontは何でもいいから一引数の関数だと仮定する。

そして関数本体内で、returnの代わりにcontを使うだけ、ってのが基本だ。

え?return使わないの?とか思うかもしれんが、先にも書いた通り、contは一引数の関数だ、としてる。と言う事はcontには必ずreturnが含まれてるんで、気にしなくて良いのだ。

つまり、ここまでならアホでも書き換えられるわけだ。

def fibs(n, cont):
　head = [0, 1]
　if n < 2:
　　cont(head[:n+1])
　else:

な?

contはfibsの計算情報を受け渡す相手だ、と言ったが、確かに本体内で計算結果、head[:n+1]をcontに受け渡している。

結果、fibsは継続をcontに受け渡してる、と言うのが既に保証されたワケだ。なんにも難しい事はない。

ここまでの要点をもう一回整理する。

関数の引数を一つ増やす。通常引数名はcontとかccにするが、いずれにせよ、この引数が受け取る前提になってるのは一引数の関数である。
関数本体で使われてるreturnを基本contに置き換える。

次はelse以降だが、末尾呼び出しを再帰に、つまり、大元の関数を引数nを一だけ減らして呼び出せば良いのは一目瞭然である。

def fibs(n, cont):
　head = [0, 1]
　if n < 2:
　　cont(head[:n+1])
　else:
　　fibs(n-1,

ここでラムダ式の出番だ。一引数のラムダ式を取り敢えず書く。

def fibs(n, cont):
　head = [0, 1]
　if n < 2:
　　cont(head[:n+1])
　else:
　　fibs(n-1, lambda u:

ここで重要なのは、contが一引数の関数なので、再帰部分には一引数の無名関数、つまりラムダ式を置いた。そして上で見たように、既に第一引数がn-1であるfibsの計算情報はcontに受け渡されてる事が保証されている。

と言うことは、だ。上のコードのラムダ式の引数、uには自然とfibsの計算結果の全てが詰め込まれてる、って事だ。言い換えるとu自体が継続だ、って事だな。

要するに、uには元々のfibsの中での変数、tailと同等の情報が受け渡されてる、と言う事だ。

結果、オリジナルのコードをuを使って真似すれば良い。returnの代わりにcontを使う事を忘れずに。

def fibs(n, cont):
　head = [0, 1]
　if n < 2:
　　cont(head[:n+1])
　else:
　　fibs(n-1, lambda u:
　　　　cont(head + [sum(i) for i in zip(u[:-1], u[1:])]))

これで完成だ。キチンと末尾再帰になっている。

さて、実行させてみよう・・・が、問題は実際実行する際、一体contに何を与えれば良いのか、と言う話がある。

これは難しくはない。簡単なやり方としては、例えばprintを使えば良い。

>>> fibs(17, print)
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597]
>>>

なんかprintがヘンな位置にあるから不思議なカンジがするだろうが、これで良い。どっちにせよ、fibsの継続はprintに受け渡される、と言う構図になっている。

他にも与えられた引数をそのまま返す、例えばlambda x: xなんかを渡しても良い。こういう引数をそのまま返す関数をつや〜にidentity関数、なぞと呼んだりもする。

2. 末尾再帰

さて、上のCPSは確かに末尾再帰なんだけど、ちと仰々しい。

ラムダ式とか出てきてるし。

理論的な話をすると、CPSというのは末尾再帰の基本ではある。が、もっと簡単に書けないだろうか、と言う話は当然出てくるわな。

ここで残念な話がある。

どんな再帰だろうとCPSを利用した末尾再帰に変換する事は可能だ。ただし、CPSを利用した末尾再帰がフツーの末尾再帰に変換が可能かと言うと・・・一応出来るとは言える。ただし、この場合、意味がある末尾再帰に変換出来る場合もあるし、出来ない場合もある、と言う事だ。

どういう事か、と言うと、Pythonのインタプリタはあまりパワーがないんだけど、末尾再帰の場合、言語処理系によっては最適化としてアセンブリレベル、ないしは仮想マシンレベルでのループに直接変換するケースが多い。これを末尾再帰最適化と呼ぶ。

例えばC言語でもgccやclangと言ったコンパイラは最適化オプションを使う事によって末尾再帰で書かれたコードをアセンブリレベルでループ構文に変換しようとする。変換しようとするのだ。

ただし、たまに末尾再帰最適化が施されない末尾再帰が存在するんだな。それが、「意味がない末尾再帰」だ。具体的にはCPSな末尾再帰で二重末尾再帰的な形式になっちゃうアルゴリズムがあったりするのだ。この場合は、フツーの再帰同様に、スタックでの効率を考えるとあまり褒められたパフォーマンスは発揮出来ない。

例えば、オーソドックスなフィボナッチ数列のコードを考える。

# 非末尾再帰
def fib(n):
　if n < 2:
　　return n
　else:
　　return fib(n - 2) + fib(n - 1)

こいつのCPSな末尾再帰は以下のようになる。

# 末尾再帰
def fib(n, cont):
　if n < 2:
　　cont(n)
　else:
　　fib(n - 2, lambda u:
　　　fib(n - 1, lambda v:
　　　　cont(u + v)))

これが「二重末尾再帰的な」コードである。確かに形式的には末尾再帰になってるが、こいつを最適化する事は出来ない。従って、「フツーの末尾再帰」に変換するのもこのままでは厄介なのだ(これもreturnの機能を考えると、再帰呼出し、即スタック破棄、と言うワケには行かない、と予想出来るだろう)。

結局、アルゴリズムの選び方によっては素直な末尾再帰を書くのが不可能な場合がある、って事だ。

この辺はあまり触らない事として、今回のフィボナッチ数列のコードはフツーの末尾再帰への変換は可能なパターンである。それを考えよう。

先にも書いたが、末尾再帰の特徴としては、

引数が一つ増えてて、それがアキュムレータとして機能してる

と言う事が挙げられる。CPS版のcontに形式的には似ている。contは関数でアキュムレータはそうじゃない、と言う違いはあるが、いずれにせよ、CPS版のコードを参考にしながら素直な末尾再帰を書いていこうと思う。

ところで、アキュムレータは累積器、だと言う話をした。と言う事は変数的に考えると初期値があっておかしくない、と言う話になる。

今までのフィボナッチ数列の初期値とは何だろうか、と言うと、head = [0, 1]がそれじゃないか、と考える事が出来る。つまり、アキュムレータの初期値を[0, 1]として、これを対象に計算していく形式が考えられるのだ。

と言う事は次のようにして書きはじめる事が出来る。

def fibs(n, acc = [0, 1]):
　if n < 2:
　　return acc[:n+1]
　else:

次に、末尾再帰である以上、nを1減らしてfibsを直接呼び出す、と言う事も同じである。

def fibs(n, acc = [0, 1]):
　if n < 2:
　　return acc[:n+1]
　else:
　　return fibs(n - 1,

あとは、ロジックは同じである。最初のコードの場合は再帰した変数tailとリスト内包表記を利用して組み上げた。CPS版は最初のコードを参考にし、継続uを変数tailの様に扱う事で同等のコードを組み上げた。今回は初期値を含んだアキュムレータaccがある。こいつを変数tailと同等に扱えば良い、と言う事に気づくのはそう難しくはないだろう。

def fibs(n, acc = [0, 1]):
　if n < 2:
　　return acc[:n+1]
　else:
　　return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])

headの代わりにacc[:2]になってるのは、今回はacc自体が再帰に伴い伸長していく。と言う事は、headの代わりにaccのアタマ要素二つ分のリストだけが常に必要だ、と言う事なだけである。

ところが、これを実行してみるとおかしな現象に出くわすだろう。

>>> fibs(0)
[0]
>>> fibs(1)
[0, 1]
>>> fibs(2)
[0, 1]
>>>

あれれ・・・fibs(2)が上手く計算出来てない。引数内でaccが上手く計算出来てないのかな?とか戸惑うかもしれない。

実はひと工夫必要なのだ。

と言うのも、次の部分を見てみよう。

if n < 2:
　return acc[:n+1]

ここは引数nに対してaccのどの部分を返すか、と言う決定をしてる部分なのだが、実はこのコードの中では素直にreturn accしてる部分が存在しない。

要するに再帰部分

return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])

でnが1減る度にaccは長くなっていってはいるが、nが2より小さくなった時点で先頭の2要素を含むリストしか返さないのである。要するにいくらaccが長くなろうとも先頭の[0, 1]しか返さないと言う・・・明らかなバグである。

単純にaccを返せば良いわけだが、結果、accの長さが2以上の場合とそれ以外に対して処理を振り分ければ良いのだ。

つまり、こう書き直す。

def fibs(n, acc = [0, 1]):
　if n < 2:
　　if len(acc) > 2:
　　　return acc
　　else:
　　　return acc[:n+1]
　else:
　　return fibs(n - 1, acc[:2] + [sum(i) for i in zip(acc[:-1], acc[1:])])

つまり、元々、引数nが2未満だった場合と、再帰の結果引数nが2未満になった場合を分ける。フラグはaccの長さを調べれば済むわけだ。

こうすれば、