再帰

「低レイヤを知りたい人のためのCコンパイラ作成入門」読書会を続けておりますが、コンパイラを作ると再帰的なプログラミングを多用します。

コンパイラは文法規則を解析しなくてはならず、文法規則自体が再帰的な定義になっているので当然そうなる訳ですが、再帰的プログラミングはどうも苦手意識があるのでこの際勉強し直すことにしました。

まず今回の読書会で使っているRuiさんの記述の中に、「自分のように再帰に慣れている者でも時々不思議な感じがする、再帰とはそういうものなのだろう」、というような文章がありました。Ruiさんでもそうなのかということで少し安心しました。再帰にはいつももやもや感があり、もやもや感を完全に払拭するまではだめなのかなと思っていたので。

また「再帰的思考法」という古い本を読んでいるのですが、その中にも勇気という言葉が出てきます。つまり何か難しい問題を解こうとして関数を書いている最中、まだ未完成な状態で自らを呼んで問題解決するという書き方なので、そんなことをやっていいのかという抵抗感がどこかにありやるには勇気を要する、それが再帰的なプログラミングの障害になるのは自分だけではなく良くあることなのだと分かり、これも安心につながりました。

昔はそもそも再帰的に書いてもいいこと自体が不思議だと思っていましたが、それについてはC言語でどのように処理されるかまで理解したことで解決しています。つまり自分を呼ぶと言ってもそれは単に関数の先頭アドレスにジャンプするだけなのでジャンプはどこにでもできるのだから当然できる、自分の中で自分を呼ぶと上書きしてしまって不具合が起きないのか気になっていましたが、C言語では引数も関数内でstaticを付けずに宣言した変数も、関数を呼ばれた時点でスタック上に新規に確保するので別のメモリを使う訳だから上書きは発生しないと理解した時から気にならなくなっていました。