関数型プログラミング事始め (26) 再帰プログラミング(2)
関数型プログラミングがはじめての方へ贈る入門の書
前節：再帰プログラミング(1) 次節：再帰プログラミング(3)
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
(3) 再帰プログラムの作り方
再帰プログラムの作り方を見ていくことにします。再帰プログラミングはどのようにして作っていくのでしょうか。
ここではOK! ISLispを使って関数型プログラミングの手習いをやっていきます。まずはislispを起動してください。なおISLisp処理系はLisp処理系の導入で紹介していますので参照してください。
> ISLisp Version 0.80 (1999/02/25)
>
ISLisp>
(a) 再帰とは、その停止条件とは
再帰とは再び自分（最初に実行した関数）に帰ってくることです。自身の関数から直接帰ってくる再帰を自己再帰と呼んでいますが、他の関数経由で自身の関数に帰ってくる他者再帰もあります。
再帰が停止する条件は(1)停止する条件があること（ベースとなる末尾項があること）、(2)再帰のとき、再帰を制御する順序がベースにより近くなっている再帰項があることです。
具体例として、前節の階乗計算factを見ていきます。
ISLisp>(defun fact (n) (if (<= n 1) 1 (* n (fact (- n 1)))))
FACT
(<= n 1)が再帰を停止する条件となり、1が末尾項(tail term)となります。このとき再帰を制御する再帰変数(recursive variable)はnであり、そのベースは(<= n 1)の1となります。
そして(fact (- n 1))が再帰項(recursive term)であり、再帰を制御する変数nの値がベースの1により近くなっており再帰項になっています。
このため、ベースの1以上で再帰項を呼び出せば、このプログラムは停止します。
(b) 数学的機能法との関係
数学的帰納法(mathematical induction)は述語(1)P(0)が成立することを証明し、(2)P(k)が成立していると仮定し、(3)P(k+1)をP(k)を使って照明します。
この数学的帰納法と再帰プログラミングは似ている構造をしています。再帰のベースが(1)のP(0)に相当し、再帰項が(3)のP(k+1)の証明で(2)のP(k)を使うことに相当します。
数学的農法では、(3)の証明が一番の眼目です。同様に再帰プログラミングでも停止する再帰項の発見が一番の眼目になります。
なお数学的帰納法はkが自然数であることが多いですが、自然数の必要はなく、全順序があり、ベースとなるボトム(⊥)があるものであれば、適用可能です。再帰プログラミングでも同様に自然数でなくても、なんらかの全順序関係があるものであれば、再帰の制御変数になり得ます。
(c) 再帰プログラミングのコツ
再帰プログラミングは数学的帰納法と同様に、停止する再帰項を発見することです。これはつまり再帰構造を発見することです。
ここで思考を広げて、日常生活を見ていくことにしましょう。日常生活には段階的な再帰が色々とあります。ええ、いっぱいあります。
例えば食事を考えます。もちろん食べるものがなくなれば食事は終わります。これがベースになり、末尾項は空っぽの皿です。食事は料理を一口食べます。そして残りの料理を食べます。これが再帰項です。プログラムは以下のようになります。
(defun 食事 (料理)
(if (空？ 料理)
空の皿
(+ 一口の料理 (食事 (- 料理 一口の料理)) ))
自然な考えで再帰プログラミングができます。人間が無意識に思考していることをそのままプログラミングするだけです。
これを繰り返しプログラミングするときは面倒です。頭の体操的に考えてみてください。繰り返しの制御変数と料理の現状（残りの料理）を別に考え、再帰プログラミングにあった空？と一口の料理、料理に対する-演算を使うことになるでしょう。面倒です。
なぜ面倒と思うのかは、順序関係が不明確だからです。つまり繰り返しプログラミングは順序関係が明確なときは作りやすいのですが、そうでないときは面倒になります（が繰り返しプログラマは（無理やり）順序を見つけるのが自然にできますので、それほど繰り返しの発見で苦痛を感じていない不感症になっているかもしれません）。
（お詫び）筆者の個人的思いから、一部の繰り返しプログラマに対して、ディスっている表現があったかもしれませんがご容赦ください。
ということでここでの結論「再帰は自然」です。
(予告) (4) 再帰プログラミング演習
次回は再帰プログラミングの演習として、いくつかの再帰プログラミングを紹介することになります。お楽しみに！
よろしければサポートをお願いします！