再帰の読み方

本記事は、「350行くらいのPythonで書くインタプリタ」（以下「minilang本」）の補足記事として書いていますが、前半は再帰一般の話ですので再帰がどうもピンとこないという方もどうぞ。

再帰に慣れてないとわかりづらいかもしれませんが、1行ずつゆっくり読んでみてください。

再帰は難しい、わからない、と書いてあるのをよく見かけます。minilang本では再帰を多用しますので多少のヒントを。ふたつあります。

まず、再帰のあるコードを読むのは（わかるまでは）簡単ではないということです。ラノベを読むようにさらさら読もうとしてわからなくても普通です。1行ずつゆっくり読みましょう。

ここからがふたつめのヒントで本題です。

おすすめな読み方

1行1行読んでるんだけどわかった気がしない、というのは、再帰を全部たどろうとしているからかもしれません^[1]。もしそうだったら、再帰する呼び出しは正しいと信じて、それ以上掘り下げない、という読み方を試してみてください。たとえばPythonでsum([1, 2, 3])を読むときはsumの中身はなんだろう、などと気にしないで「ちゃんと足してくれるだろう」と思って読みますよね（たいていは）。それと同じように読んでみる、ということです。

0からnまでの整数の和を返す以下の関数で説明します（これはminilangではなくPythonです）。

def to_n(n):
    if n == 0: return 0
    return n + to_n(n - 1)

to_n(5)の呼び出しを考えます。5 == 0ではないのでreturnで5 + to_n(4)を返そうとします。to_n(4)は正しく10を返してくれる、と信じると、to_n(5)は15になります。正しいですね。かんたん！以上です！

それでいいの？と思うかもしれませんが、呼び出しを続けていくと最後はnが0になってreturn 0が0を返すところまで行きつきます。これは正しい。あとは全部遡って芋づる式に正しいというわけです。再帰が止まるところを「基底」と言います。基底を確認することも大事ですが、誰かの書いたコードを読むときには基底もちゃんと定義されてるはずです。そうでないといつまでたっても再帰が止まらないので。

この考え方は再帰を書くときにも応用できます。to_n(5)を求めたいとき、何もないところから考えるのではなく、to_n(4)がわかっているものとして考えればいいわけです。もっと一般化していえば、to_n(n)を求めたいときにto_n(n-1)はわかっているものとして考えてよいということです。学校で習った数学的帰納法を思い出した方もいるかもしれません。同じしくみです。あと、自分で書くときは基底を忘れずに定義しましょう。大事です。

この読み方に慣れると再帰を読むのが（書くのも）うんと楽になります。むしろ再帰で書いてある方が素直、と思えるくらいに。ちょっとややこしいことを書こうとしてこれは再帰で書けるやつだな、と思って「n - 1のときはわかってるものとして～～」と書いていくと思ったより単純で、ほんとにこれで動くのか？と思って半信半疑なのに動かすと動いてしまう、ということもしばしばです。普通のプログラミングでは動くと思ってても動かないのに！何それ！

初めからたどっていく方法

でもやっぱり心配だ、という場合は浅い再帰から全部試していってみましょう。腹落ちするまでやっておくのもよいかと思います。いちばん浅いのは基底で、to_n(0)つまり0ですね。to_n(1)は1 + to_n(0)ですから、to_n(0)の結果が使えて 1 + 0 = 1 となります。続きも芋づるで以下のようになります。

to_n(0) = 0
to_n(1) = 1 + to_n(0) = 1 + 0 = 1
to_n(2) = 2 + to_n(1) = 2 + 1 = 3
to_n(3) = 3 + to_n(2) = 3 + 3 = 6
to_n(4) = 4 + to_n(3) = 4 + 6 = 10
to_n(5) = 5 + to_n(4) = 5 + 10 = 15

実際の呼び出しではこれを下の方からたどっているわけです。ひとつ前の結果がわかっていればちゃんと計算できる感じがつかめたでしょうか？

全部遡ってみる

やっぱり「再帰を全部たどる」をそのままたどってみたい？それもありだと思います。両方わかってるのが理想的でしょう。この場合、再帰を追いかけるとき関数全体を見ていると頭の容量が足りなくなってしまうので、特に再帰呼び出しの部分に注目し、呼び出しのときどんな呼び出しをしているかを追いかけます。returnの部分ですね。さっきやったのをひっくり返してつなげていく感じです。

  to_n(5)
= 5 + to_n(4)
= 5 + (4 + to_n(3))
= 5 + (4 + (3 + to_n(2)))
= 5 + (4 + (3 + (2 + to_n(1))))
= 5 + (4 + (3 + (2 + (1 + to_n(0)))))

to_n(0)は0ですからこうなります。

= 5 + (4 + (3 + (2 + (1 + 0)))) 

再帰はここで止まります。ここでおわりにしてもOKなのですが、関数呼び出しから帰っていくところまで追いかけてみましょう。

= 5 + (4 + (3 + (2 + 1)))
= 5 + (4 + (3 + 3))
= 5 + (4 + 6)
= 5 + 10
= 15

再帰にもいくつかのパターンがあって、シンプルなものならこうやって最後までたどることができます。そうでないものもあって、フィボナッチ数列なんかは２・３回たどったらもう書ききれなく（書く気がしなく）なってくるでしょう。そういう場合も浅い再帰から書いていく方式なら書けることもあります。

最初に書いた通り、（感覚がつかめるまでは）簡単なものではないのでわかるまでいろいろ練習してみるとよいかと思います。再帰を徹底的にやってみようと思ったらminilang本でも紹介したScheme手習いがおすすめです（ただしクセあり注意）。

minilang本の例でやってみる

この節はminilang本を読んでくれている方向けの節となります。

minilangのべき乗（^）を構文解析するParser._parse_power()というメソッドがあります。これを例にとって説明します。このメソッドを取り上げたのは、自分自身を直接呼んでいるのと、第２弾としてはちょうどいい程度に処理があるためです。

    def _parse_power(self):
        power = self._parse_primary()
        if self._current_token != "^": return power
        self._next_token()
        return ["^", power, self._parse_power()]

Parser._parse_power()が2 ^ 3 ^ 4 ^ 5を解析する場合を例にとって説明します。この場合、2 ^ 3 ^ 4 ^ 5が引数として渡されるわけではないのですが、ちょっと思い浮かべづらい・書きづらい^[2]ので説明のために、2 ^ 3 ^ 4 ^ 5を_parse_power()で解析することをparse_power(2^3^4^5)と書くことにします（先頭のアンダースコアも省略）。

まずは掘り下げないやりかたから。

parse_primary(2^3^4^5)ではまずpowerに2が入ります。次のトークンは^なので_next_token()に進みます。returnまで来ると2と^はすでに読んでいますので残りの部分は3 ^ 4 ^ 5です。なのでreturnは["^", 2, parse_power(3^4^5)]を返すために、_parse_power()を再帰的に呼び出します。このとき、もう一度parse_power()の中身を追いかけずに、「きっとparse_power(3^4^5)はちゃんと正しく["^", 3, ["^", 4, 5]]を返してくれる」と信じます。すると["^", power, self._parse_power()]は["^", 2, ["^", 3, ["^", 4, 5]]]となり、正しく右結合なASTが得られることがわかります。

言葉で書くと長たらしいですね^[3]。図式的に書くとこんな感じです。どうでしょう？

parse_power(2^3^4^5) → ["^", 2, parse_power(3^4^5)] → ["^", 2, ["^", 3, ["^", 4, 5]]]

「_parse_power()はちゃんと正しく["^", 3, ["^", 4, 5]]を返してくれる」が最初は思い浮かべづらいかもしれません。基底から始めてたどってみましょう。

基底は5の解析です。この場合、powerに5が入り、それを返して終わりです。

次に、4 ^ 5を解析します。powerに4が入った後、次に来るのが^なので["^", 4, parse_power(5)]を返すために_parse_power()を呼びます。ここでは5を解析することになりますので、さっき考えた通り5が返ってきます。self._parse_power(5)の部分を5で置き換えて、["^", 4, 5]が値となります。

さらに3 ^ 4 ^ 5を解析する場合も同様に考えると["^", 3, parse_power(4^5)]を返そうとします。parse_power(4^5)は今やったとおり["^", 4, 5]になりますので3 ^ 4 ^ 5の解析結果は["^", 3, ["^", 4, 5]]となります。

2 ^ 3 ^ 4 ^ 5の解析でも3 ^ 4 ^ 5の解析結果を利用して["^", 2, ["^", 3, ["^", 4, 5]]]が返されることがわかります。

まとめるとこうなります。

parse_power(      5) → 5
parse_power(    4^5) → ["^", 4, parse_power(    5)] →                   ["^", 4, 5] 
parse_power(  3^4^5) → ["^", 3, parse_power(  4^5)] →          ["^", 3, ["^", 4, 5]]
parse_power(2^3^4^5) → ["^", 2, parse_power(3^4^5)] → ["^", 2, ["^", 3, ["^", 4, 5]]]

基底以外はひとつ前の結果を利用して置き換えているところに注目してください。

ここまでわかったらもう全部遡って考えることもできるようになっているのではないでしょうか？

2 ^ 3 ^ 4 ^ 5がを解析する場合、まずpowerに2が入り、次のreturnの値は["^", 2, self._parse_power()]となります。この_parse_power()の呼び出しではpowerに3が入り、次のreturnの値は["^", 3, self._parse_power()]となります。組み合わせると、最初のreturnの値は["^", 2, ["^", 3, self._parse_power()]]となります。もう一度同じことを繰り返すと["^", 2, ["^", 3, ["^", 4, self._parse_power()]]]となります。最後の_parse_power()の呼び出しでは、powerに5が入り、続きが"^"ではありませんので5を返します。

コンパクトに並べるとこうなります。

  parse_power(2^3^4^5)
→ ["^", 2, parse_power(3^4^5)]
→ ["^", 2, ["^", 3, parse_power(4^5)]]
→ ["^", 2, ["^", 3, ["^", 4, parse_power(5)]]]
→ ["^", 2, ["^", 3, ["^", 4, 5]]]

さて

このメソッドを取り上げたのは、自分自身を直接呼んでいるのと、

直接呼んでない場合はどうしましょうか。たとえばこの箇所。カッコでくくった式（expression）の中にさらにカッコが出てくると間接的に自分を呼ぶことになります。

    def _parse_primary(self):
        match self._current_token:
            case "(":
                self._next_token()
                exp = self._parse_expression()
                self._consume_token(")")

この場合も、まずは_parse_expression()が正しい結果を返してくれる、と信じて局所的に動作を理解しましょう。例を挙げて考えるときはできるだけ簡単な例で。1 + (2 + (3 + 4))くらいあれば十分です。なんなら((1))でも。

とはいうものの、直接呼んでない場合はかえって「再帰呼び出しは正しいと信じて読む」が自然とできるような気もします。sum([1, 2, 3])を読むのと同じように。

まとめ

再帰的に呼び出しているからと言って遡って追いかけようとせず、正しい値を返してくれると信じて読んでみるといいよ、たいていはそれで充分、というお話でした。普通の関数呼び出しだとそういう風に読むことも多いと思いますが、再帰だとすぐ目の前に呼び出したい関数があるわけで、つい読もうとしてしまう、ということかもしれません。

きっとこれで再帰の動きを少し具体的にイメージできるようになっていると思います。再帰は使いどころで使うととても強力な道具ですので自分で書くときにもこの考え方を生かしていただければと思います。

では、楽しい再帰ライフを！（何

脚注

1. 私の頭の中にいる再帰が苦手な人のイメージです。「再帰は難しい、わからない」というのも、教える側のひとが書いてるのしか見たことがありません。もしかするとこの記事の対象読者はこの世に存在しないかもしれません。

2. オブジェクト使って属性に情報を覚えさせるように書くとこうなってしまうのはひとつの弱点で、関数型っぽく全部引数で渡すようにするとこういうときは考えやすくなります。構文解析を関数型で書くと「パーザコンビネータ」になります。

3. 逆に見ると、文章にすると長たらしくなることをコードではコンパクトに圧縮して書いているわけです。これが「ラノベを読むようにさらさら」読めない理由のひとつです。