関数型プログラミング事始め (5) 再帰の苦難
関数型プログラミングがはじめての方へ贈る入門の書
前節：配列の苦難 次節：ラムダの苦難
参考書：
・五味 弘「はじめてのLisp関数型プログラミング」技術評論社(2016)
・大山口 通夫、五味 弘「プログラミング言語論」コロナ社(2008)
・五味 弘「関数型プログラミングと数学(ITと数学)」技術評論社(2021)
(3) 再帰プログラミング - 呪いと祝い
再帰プログラミングは自分の関数の中で自分の関数を直接的、間接的に呼び出すプログラミングです。
イメージとしては、関数f(n)をステップのf(n-1)とベースのf(0)で定義するようなイメージになります。f(n)はf(n-1)で定義され、f(n-1)はf(n-2)で定義され、以下同様にこのステップを繰り返すことになります。
そこで最終的にベースのf(0)になれば、この定義による値から元のnまで戻って計算することになります。
(例) 再帰プログラミングの階乗計算
以下に階乗計算を再帰プログラミングしたものと繰り返し文でプログラミングした例を示します。
例. 階乗計算
(1) 再帰プログラミング
int fact(int n){
if (n == 0) return 1; // ベースのf(0)の定義
else return n * fact(n - 1); // ステップのf(n-1)の定義
}
fact(3) → 3 * fact(2) → 3 * 2 * fact(1) → 3 * 2 * 1 * fact(0) → 3 * 2 * 1 * 1 → 6
(2) 繰り返し文
int fact(int n){
int ret = 1;
for (int i = 1; i <= n; i++) ret = ret * i;
return ret;
}
fact(3) → ret = ((1 * 1) * 2) * 3 → ret = 6
(1)の再帰プログラミングではベースとなるfact(0)の値を1と定義して、ステップのfact(n-1)をn*fact(n - 1)と定義しています。
このときにf(3)を実行すると、nはベースの0ではありませんので、次のステップの3*fact(2)になります。そこでfact(2)の実行は同様に2*fact(1)となり、fact(1)は1*fact(0)となり、fact(0)はベースの定義により1を返します。この結果、fact(1)は1*1になり、fact(2)は2*(1*1)になり、fact(3)は3*(2*(1*1))になり、結果として、6を返します。
一方、繰り返し文によるプログラミングは制御変数 i によって繰り返しを制御することになります。再帰プログラミングでは使用していない制御変数が繰り返しプログラミングでは必要になります。
（考察）再帰プログラミングの呪いと祝い
再帰プログラミングは繰り返しプログラミングと比較して、制御変数が不要になり、その結果、シンプルな構造になります。これは再帰プログラミングの利点です。
しかし再帰の考えに慣れていない人にとっては、考え方をパラダイムシフトする必要があり、これが再帰の考えを難しいものと思う原因になっています。（慣れれば簡単です!?）。
それに再帰プログラミングはスタックを使用して実装されるので、スタックを使用しない繰り返し文と比較して実行が遅くなる可能性があります。しかし現在は速度よりもシンプルさの方が重要です。あなたも富豪プログラミング(*)をしましょう。
(*) 富豪プログラミング
メモリやCPUを湯水のように使う富豪だけに許されるプログラミング。最近はメモリが大容量になり、CPUが高速化されているので、一般人でも富豪プログラミングできる時代になってきています。
（考察）関数型プログラミングでは繰り返しは悪なのか
繰り返し文は用法用例を守れば悪いものではありません。確かに制御変数というローカル変数を使いますが、その変数の影響範囲内で副作用を生じないようにすれば、問題ありません。上記の例であれば、副作用を生じていません。
しかし繰り返し文では副作用を生じる危険性は高くなります。制御変数以外の変数を使う機会が増え、どうしても副作用があるプログラミングをしてしまいがちになります。
それに制御変数による副作用も考えられます。例えば制御変数をとあるデータ構造のインデクサ（データ構造の位置を示す変数）として使う場合は、そのデータ構造に対して、副作用を与える危険性も出てきます。
このように繰り返しプログラミングは絶対的な悪ではありませんが、悪の道に落ちてしまう誘因になります。細心の注意を持って繰り返しを使いましょう。
ということで今回の結論「再帰は一度は使ってみて」以上です。
(次回予告) (4) 高階関数の苦難
次回は関数型プログラミングの特徴である高階関数が難しいという苦難です。
参考：プログラミング言語はどれがお得？(前編）｜五味弘 (note.com)
参考：プログラミング言語はどれがお得？(後編）｜五味弘 (note.com)
よろしければサポートをお願いします！