再帰処理について調べてみた

お疲れ様です。Y研究員です。８月も下旬になってきました。夏休みの宿題もそろそろ終わらせたい？着手したい？時期ですね。

しぶとく続けている古典な教科書の『写経』の続きです。古い教科書なので古い教育プログラミング言語、Pascalの方言が使われています。ChatGPT-4を使ってC言語に変換して、それを『写経』しています。Pythonでもできると思います。自分で自分を呼び出す再帰の章を終えたので、分かった事をまとめます

1. デバッグが難しい

2. 現代ではあまり推奨されていない

3. 再帰で解くべき問題がある

１はバグを仕込むとかなり怪しい挙動をするので、デバッグが難しいです。特に終了条件を間違えると延々とリソースを食いつぶしてクラッシュします。またロジックが特殊になるので、想定しない出力も普段とは毛色が違い、慣れが必要と思いました。

現代ではデバッグが難しかったり、簡単にリソースを食いつぶすので推奨されていないという記事を見かけました。Pythonは再帰関数の呼び出し回数を制限しているくらいです。逆に関数型プログラミング言語のHaskelは再帰を重要視していると分かりました。

最後に再帰で解くべき問題についてです。ChatGPT-4に聞いてみたところ、直感的に再帰の方がわかりやすい例が出てきました。フィボナッチ数列やフラクタルの描画は明らかに再帰で解く問題です。迷路や数独を解くプログラムなんかは面白そうです。島を探す課題は画像処理ですね。参考までにChatGPT-4の回答を日本語訳して添付しておきます。

階乗の計算: 数字の階乗を見つける。n! = n * (n-1)!。
フィボナッチ数列: n番目のフィボナッチ数を計算する。
ハノイの塔: より大きなディスクがより小さなディスクの上にない制約の下で、異なるサイズのディスクを1つのペグから別のペグに移動するクラシックなパズル。
二分探索: 望ましい値が見つかるまで配列を繰り返し半分に分ける。
木の走査: 例えば、バイナリツリーの中順、前順、後順の走査。
グラフの走査: 深さ優先探索(DFS)や幅優先探索(BFS)。再帰は特にDFSで使用されます。
分割統治アルゴリズム: マージソートやクイックソートのようなもの。
バックトラッキングの問題:
N-Queens: N個のクイーンをN×Nのチェスボードに配置する。どの2つのクイーンも互いに脅威を与えないようにする。
セットのすべての可能な順列や組み合わせを生成する。
数独ソルバー。
動的プログラミングの問題: これらの多くは繰り返しで解決できますが、再帰を使用していると一部の問題は概念化が簡単になることがあります。
コインの変更問題。
最長共通部分列。
行列のチェーン乗算。
構文解析の問題: 再帰的降下パーサーは、文法ルールに基づいて構文解析タスクをより小さな部分構文解析タスクに分解します。
数値の冪乗の計算: x^y = x^(y/2) * x^(y/2) がyが偶数の場合のコンセプトを使用して、xのy乗を効率的に計算する。
フラクタルの生成: Sierpińskiの三角形やMandelbrotセットのようなパターンの生成。
Ackermann関数: 成長が非常に速い計算可能な関数。アルゴリズムの分析で時々使用されます。
括弧の生成: 与えられたペア数のためのすべての組み合わせの整形された括弧を生成する。
最大公約数(GCD)の探索: ユークリッドのアルゴリズムを使用して。
ナップサック問題: アイテムに価値と重量があり、重量制限を超えずに価値を最大化しようとする0/1ナップサック問題の再帰的な解決策。
バランスの取れた分割問題: 2つの部分集合にセットを分ける。両方の部分集合の数の合計が同じになるように。
迷路の解決: 迷路の出発点から目的地までのパスを見つける。
行列での島のカウント: 1（陸）と0（水）の2D行列が与えられた場合、島の数をカウントします。
回文の分解: 文字列を回文の部分文字列に分解する。

ChatGPT-4

写真は大洗の「島」です。あんこう鍋で有名ですね。寒くなってきたら行きたいです。

それではまた！