阿珏酱

上の多くの回答を見ましたが、ほとんどは説明に偏っています 再帰 の現象についてであり、なぜ再帰を使用するのか、再帰の考え方が何であるかについては説明されていません。最近、ちょうどいくつかのことを見たので、整理してみました。間違いがあれば、遠慮なく指摘してください。

• 再帰とは何ですか？

1. 定義

Wiki [1]： 再帰 とは、自己相似的な方法でアイテムを繰り返すプロセスです。

コンピュータに具体的に言うと [2]：

再帰 （英語：Recursion）は、関数の定義の中で関数自身を使用する方法を指します。

英語のRecursionは語源的に「re-（再び）」+「curs-（来る、起こる）」であり、繰り返し発生する、再現されるという意味です。一方、対応する日本語の翻訳「再帰」は二つの意味を表しています：「再」＋「帰」。この二つの意味こそが再帰の考え方の本質です。この観点から見ると、日本語の翻訳の方がより的確です。

2. ループとの違い

上記のWikiの定義を見ると、通常言われる無限ループに似ているように見えますが、彼らの違いは何でしょうか？

再帰は静の中に動があり、行き来があります。
ループは動と静が一体で、行きはあっても帰りはありません。

例を挙げると、あなたに鍵が一つ渡され、あなたはドアの前に立っています。この鍵で何扉開けられるか尋ねられます。

再帰：あなたは目の前のドアを開けると、部屋の中にさらに一つのドアがあることがわかります（このドアは前に開けたドアと同じ大きさかもしれません（静）、または少し小さいかもしれません（動））。あなたは近づいて、手に持っている鍵がそれを開けられることを発見します。ドアを押し開けると、さらに一つのドアがあり、あなたは開け続けます。。。何度か後、目の前のドアを開けると、ただ一つの部屋があり、ドアはありません。あなたは元の道を戻り、戻るたびに一回数え、入口に到達したとき、あなたはこの鍵で何扉開けたか答えることができます。

ループ：あなたは目の前のドアを開けると、部屋の中にさらに一つのドアがあることがわかります（このドアは前に開けたドアと同じ大きさかもしれません（静）、または少し小さいかもしれません（動））。あなたは近づいて、手に持っている鍵がそれを開けられることを発見します。ドアを押し開けると、さらに一つのドアがあり、（前のドアが同じなら、このドアも同じです。二番目のドアが一番目のドアより小さければ、このドアも二番目のドアより小さくなります（動静一体、変化がないか、同じ変化がある））。あなたはそのドアを開け続けます。。。このようにしてずっと進み続けます。入口にいる人は、あなたが戻ってきて答えを教えてくれるのを待っているのです。

3. 再帰の考え方

再帰とは、行き（再帰）と帰り（帰還）があることです。

具体的に言うと、なぜ「行き」が可能なのか？
これは、再帰の問題が同じ解法で似ているが少し異なる問題に答えることができる必要があります（上記の例の鍵が後のドアの鍵を開けることができるように）。

なぜ「帰り」が可能なのか？
これは、これらの問題が大きいものから小さいものへ、近いものから遠いものへと進む過程で、終点、臨界点、ベースラインがあり、その点に達したら、さらに小さく、遠くに進む必要がない点がある必要があります。そして、その点から元の地点に戻ります。

このブログ記事[3]の著者は次のように要約しています：

再帰の基本的な考え方は 大きな問題を小さな類似のサブ問題に変換して解決することです 。関数の実装時、大きな問題を解決する方法と小さな問題を解決する方法はしばしば同じ方法であるため、関数が自分自身を呼び出す状況が生じます。また、この問題を解決する関数は 明確な終了条件を持つ必要があります 。これにより、無限再帰の状況が発生しなくなります。

4. いつ再帰を使用する必要がありますか？

いくつかの問題の定義自体が再帰的な形式である場合、再帰を使用して解決するのが最も適しています。

コンピュータ専攻の学生が最もよく知っているのは「 木 」の定義です[4,5]。他にもいくつかの定義、例えば階乗、フィボナッチ数列[6]などがあります。これらの問題を再帰で解決することで、しばしば数行のコードで見た目にはかなり「恐ろしい」問題を解決できます。もちろん、再帰の性能問題は別の話であり、スタックの割り当てや関数呼び出しのコストは具体的な実践において考慮すべきことです。しかし、今は再帰の考え方について議論しているので、まずはそれらを置いておき、再帰の美しさを楽しみましょう。