このブログの読者は会社員と大学生が多く、どちらもいわゆるビジネス・アワーに訪れる人たちが多い。何かしらの問題に遭遇し、検索の結果、目的の投稿へ辿り着き、答えを見つけて帰っていくのだろう。
特定の記事は、ブックマークされることがあるかもしれない。繰り返し参照される記事だけはBounce rateが緩やかに上昇していく。
週末に投稿したmatch/nmatchが、このブログでは特異なアクセス傾向を示していることに気付いた。Avg. Time on Pageは当初4～5分前後だったものが、今日は後編が10分を超えた。
同時にBounce rateはどちらも9割近かったものが、昨日を境に後編だけ復帰した。
42関連の投稿は、これまでにない傾向を示している。おそらく勉強している人達が繰り返し訪れ、日、月曜日を境に前編を卒業して、後編へと前進したのではないかと解釈している。
私は読者に迎合するつもりはないのだが、熱意には応えたいと思う。要はお節介だ。
match/nmatchで詰まっている人の原因は再帰の理解にあるのではないかと考えている。今回はmatch/nmatchの話題に関連し、再帰を説明してみようと思う。
今回の問題はPiscineの問題ではなく、独自のものだ。あくまでも再帰の説明に焦点を絞っている。
準備
Pythonに限らず、言語や開発ツールのインストール不用で、直接オンラインでコードを実行することのできる環境が用意されている。例えば次のサイトだ。サンプル・コードをコピーし、試行錯誤しながら参照してほしい。
paiza.io
問題
正負を問わず、任意の数が一つ与えられる。符号を含め、一桁ずつ文字列配列に格納せよ。
例１：-130が与えられたとき→[-, 1, 3, 0]
例２：130が与えられたとき→[1, 3, 0]
これはitoaと呼ばれる典型的な練習問題だ。与えられた文字列を数値へ変換する、atoiと呼ばれる類題も典型的な練習問題で、こちらは42SV Piscine 2017 Day03 Exercise 08で採用されている。
ループで解く考え方
まず再帰は考えず、ループで解く方法を考える。数字を一文字ずつ処理したい。そのためには各桁の数値を取得する必要がある。数値（int型）で与えられるので、文字列のように処理することはできない。まず桁を分解する必要がある。考えられるパターンは二通りある。
| 後から分解 | 100 | 30 | 0 |
| 前から分解 | 1 | 13 | 130 |
「後ろから分解」する場合は、一見分かりやすい。各桁の数毎に分解できれば、その先頭の文字を拾えばよいからだ。各桁に分解するにはで割れば良い。このnを取得するには、桁数を取得しなければならないのだが、それは文字列の長さだ。これから文字列に直さなければならないのに、この手は使えない。
「前から分解」する場合、文字列の長さを知る必要はない。各桁の数毎に分解したら、その末尾の文字を拾えばよいからだ。末尾の数を拾うには、10で割った余りを取得すればよい。
与えられた数をnとすれば、そのプログラムはこのようになるだろう。
while n > 0: rev.append(int(n % 10)) n = int(n / 10)
ここで3行目に注意。最初はn=130なので、ここでn=13になる。先のパターンでの順序が逆転している。そして、このループの結果はrev=[0, 3, 1]となる。正しい結果を得るには、この配列を逆転しなければならない。関数を用いることなく配列を逆転するには、新たな配列に正しい順序で格納し直さなければならない。新たな配列をretとすれば、プログラムは次のようになる。
len_rev = len(rev) - 1 ret = [] for i in range(len_rev, -1, -1): ret.append(rev[i])
このループの結果、ret=[1, 3, 0]が得られる。
最後に符号の処理。もしn=-130だった場合は、配列に符号を与えなければならない。どのタイミングで与えるべきだろうか。十分に考えた上で、末尾のサンプル・コードを確認してほしい。
再帰で解く考え方
再帰
再帰の意味と特徴を確認しておく。再帰というのは、関数が処理中に、自分自身を呼び出す仕組みだ。処理の流れは同じ関数の入れ子構造的になり、処理中にループが含まれていなくとも、ロジック全体はループ的な構造になる。
入れ子構造の中で、一番最後の関数が、一番最初に結果を返す。最後から2番目の関数が、この結果を受け取り、処理する。その結果を順番に引き渡しながら、一番最初の関数に戻り、最初の関数は最終的な結果を出力する。
なぜ再帰を利用するのかと言えば、一つはアルゴリズムのロジックそのものが再帰である場合だ。例えばmatch/nmatchのバックトラック法が代表例だ。再帰を伴うアルゴリズムは他にもある。
ありきたりなプログラムで再帰を用いる典型的な目的の一つは、ロジック構造をシンプルにすることだ。
例えば「ループで解く考え方」にはループが2つ登場した。またループの入れ子構造も無用な複雑さを持ち込み、多重ループとして嫌われることが多い。コード・レビュー中に3～4重に入れ子されたループが見つかったら、おそらく理由を問い詰められるだろう。
再帰は、そのようなロジック構造をシンプルにしてくれる。ロジック自体をシンプルにするのではない。複雑さは変わらない。その見た目（構造）をシンプルにしてくれる。結果としてプログラムもシンプルになる。
図は「ループで解く考え方」を再帰構造に直したものだ。
黒線が関数内部の処理の流れを表している。青線が再帰呼び出し、再帰された処理の流れは、呼び出し元の関数へつながる。その処理中、赤線で数値を文字列配列へ格納している。
「ループで解く考え方」には数値から文字列を取り出す、取り出した配列を逆転させる、二つのループが存在した。再帰の一連の流れは、これらのループを包含していることが分かるだろうか。
関数は呼び出し順に[0, 3, 1]の数字を取得している。ここまでは文字列を取り出すループと同じ流れだ。そして最後に呼び出された関数が、最初に数字を代入している。最初に呼び出された関数が、最後に数字を代入している。結果として順番に[1, 3, 0]と文字列が格納される。この構造は配列を逆転させるループを代役している。
この構造をプログラムで表すと、次のようになる。ループで考える場合と比べて、かなり簡素なコードになる。符号の処理を含めた全体はサンプル・コードを確認してほしい。
def itoa(n, ret): p = int(n / 10) if p > 0: itoa(p, ret) ret.append(int(n % 10))
短いプログラムが好まれる。それは読みやすく、理解しやすいからだ。文章にしても長文より、箇条書きの方が理解しやすいだろう。
また長いプログラムは、それだけタイプする必要があるということだ。ミスタイプも起きやすいし、エラーも生じやすくなる。これは生産性の問題だ。短く正確なプログラムは、それだけ生産性が高くなる。
無用に長いプログラムも嫌われるのだ。再帰はプログラムをシンプルにしてくれる。
余談
ここで一度match/nmatchを振り返ってほしい。どちらの処理でも再帰を用いている。これらの再起をループに書き直したら、どのような構造になるだろうか。多分、手に負えない。
再帰を用いたから「あの程度」の複雑さで収まっていることが分かるだろう。
今回は再帰の説明を優先したために、一つ配慮したことがある。今回紹介した再帰関数には戻り値がない。引き渡した配列をポインタ的に参照させることで、戻り値を不要とした。
ほとんどの場合において、再帰関数は呼び出し元へ戻り値を返す。端的にint(1 or 0)を返す関数でも、膨大な呼び出しと、その結果が集約されることで、再帰の発端となった関数の戻り値は、何らかの集計結果になることがある。これがまさにnmatchで実践していることだ。
Day04 Exercise 04にフィボナッチ数列の問題がある。再帰を用いる解法では、２つの処理に分かれる再帰を用いることになる。戻り値のある再帰の説明として、後日の投稿で説明しようと思う。
By Odin, by Thor ! Use your brain !!!
サンプルコード
ループで解く
def itoa(n): if n < 0: is_minus = True n *= -1 else: is_minus = False rev = [] while n > 0: rev.append(int(n % 10)) n = int(n / 10) if is_minus == True: rev.append('-') len_rev = len(rev) - 1 ret = [] for i in range(len_rev, -1, -1): ret.append(rev[i]) return ret n = -130 print(itoa(n)) n = 130 print(itoa(n))
再帰で解く
def itoa(n, ret): if n < 0: ret.append('-') n *= -1 p = int(n / 10) if p > 0: itoa(p, ret) ret.append(int(n % 10)) n = -130 r1 = [] itoa(n, r1) print(r1) n = 130 r2 = [] itoa(n, r2) print(r2)
