次へ 前へ 目次へ 佐々木将人の個人ページへ
10 ループではなく再帰
コンピューターにとって，繰り返すことは自然ですが，再帰というのは必ずしも自然ではありません。情報処理技術者試験で出題されていたアセンブラにCASLというのがありましたが，これの制御構造に関する命令群は「（命令は何もなければ）順に実行する」「条件によって次に実行すべきアドレスを変えるor実行すべきアドレスを無条件で変える」でしたので，繰り返し・ループは自然に実現できますが，再帰というのは実現に工夫が必要です。
これを受けて，高級言語でもループはたいていできるようになっていますが，再帰については必ずしも当然にできるわけではなく，プログラマーの側でロジックを書いてあげるなどの工夫が必要になります。
Erlangにはループがないようなので再帰を使うしかありません。Lispにはループはありますが，再帰も使えます。
再帰というのは，与えられた課題に対して，真向からそれを解くのではなく，一段階簡単にした問題が「解けた」ということにして，その解けた問題に一段加えると問題に対する答になるよねというアプローチです。一段階簡単にした問題を解くのに，自分自身を利用するのが特徴です。
たとえば，リストを与えて，リストの中の要素の数を数える関数というのを自分で書いてみることを考えます。
※たいていの処理系はリストの中の要素の数を数える関数を用意しています。それを利用しないで自分で書いてみるという話です。
まずループを使う場合には，数を記録するカウンターを用意して，リストの何番目かを指定すればその要素を返すという関数も用意して，カウンターを0にセットして，リストの（カウンターの値……最初は0）番目を取り出す関数を動作させ，要素があればカウンターを1増やして，リストの（カウンターの値）番目を取り出す関数を動作させ……というのを繰り返します。要素がなければその時点でのカウンターの値を返して終了です。
ところで，普通は「リストの（カウンターの値）番目を取り出す関数」も用意されているのが普通ですが，これがなかったらどうします？Lispだったらcarとcdrしかリストを操作する関数がなかったら……。
仮に，リストの中の要素の数を数える関数が，(nagasa X）で求められたことにしてしまいます。そして問題を一段簡単にして，(cdr X) をnagasaという関数に与えて，それに1を加えたものが最終的な答という理解をします。
とりあえずこうなります。
(defun nagasa(X) (1 + nagasa(cdr X)))
ただし，このままだと Xのcdrをとってさらにそのcdrをとって……というのが永遠に続くことになってしまって，いつまでたっても答が出ないことになります。cdrをとってnilだったらそれ以上cdrをとるのは止めなきゃいけませんし，よく考えれば，そもそも空のリストを渡した時には0を返さなければなりません。
というので，そのことを加味すると
(defun nagasa(X)
(cond (((null X) 0)
(t (1 + nagasa(cdr X)))))
ということになります。nagasaという関数を定義する中で，nagasaという関数を呼び出している，これを再帰と言います。
慣れると再帰はわかりやすいですし，ループの時のようにカウンター用の別の変数を用意したり，それを初期化したりなんてことも不要なので，あらぬミスを防ぐこともできます。一方，コンピューターの側に再帰という考え方が自然に備わっていない以上，機械語に落とす時には，コンピューターの側がそのあたりをうまく処理していることになります。具体的に言うと，例えば要素数5のリストをXとしてnagasa(X)と呼び出した時，
nagasa(X)はnagasa(cdr(X))に1を加えたものだな
nagasa(cdr(X))はnagasa(cdr(cdr(X)))に1を加えたものだな
nagasa(cdr(cdr(X)))はnagasa(cdr(cdr(cdr(X))))に1を加えたものだな
nagasa(cdr(cdr(cdr(X))))はnagasa(cdr(cdr(cdr(cdr(X)))))に1を加えたものだな
nagasa(cdr(cdr(cdr(cdr(X)))))はnagasa(cdr(cdr(cdr(cdr(cdr(X))))))に1を加えたものだな
nagasa(cdr(cdr(cdr(cdr(cdr(X))))))は0だな
だからnagasa(cdr(cdr(cdr(cdr(X)))))は0+1で1だな
だからnagasa(cdr(cdr(cdr(X))))は1+1で2だな
だからnagasa(cdr(cdr(X)))は2+1で3だな
だからnagasa(cdr(X))は3+1で4だな
だからnagasa(X)は4+1で5だな
という経過をたどって5を返すわけですので，この経緯をコンピューターの側が覚えておくように仕掛けているわけです。
再帰については，一番簡潔な場合，上の例で言うなら空のリストを渡した場合，言い換えれば「これ以上は再帰的定義は無理ですよ」という場合の条件をまず明記することが重要で，その上で，その他の場合について再帰的に定義する，自分自身を使って定義するということを行えば，プログラムが止まらない……なんてことにはならないでしょう。
※もっとも私個人は，先に再帰的な定義をしてから，終了条件を書くことが多いようです。
（2023.6.4. 初版）
次へ 前へ 目次へ 佐々木将人の個人ページへ