再帰入門

再帰は、関数が自分自身を呼び出して問題を解決するプログラミング手法です。向かい合った2枚の鏡を覗き込むようなものだと考えてみてください。それぞれの反射には同じ像のより小さなバージョンが含まれており、反射が小さすぎて見えなくなるまで無限ループを作り出します。

すべての再帰関数が正しく動作するためには、2つの不可欠な要素が必要です。ベースケースは再帰を停止させる条件であり、鏡の反射が小さくなりすぎて無視できるレベルになる地点のようなものです。ベースケースがなければ、関数は自分自身を無限に呼び出し続け、最終的にプログラムをクラッシュさせます。

再帰ステップとは、関数が元の問題を修正したバージョンで自身を呼び出す段階のことです。関数が自身を呼び出すたびに、より小さく、またはより単純な問題に取り組む必要があり、徐々にベースケースへと近づいていきます。

積み上げられた書類の中から鍵を探しているところを想像してみてください。一番上の書類を確認し、そこに鍵がなければ、残りの束（1枚少なくなった状態）に対して同じことを繰り返します。鍵が見つかるか、確認する書類がなくなるまで、このプロセスを繰り返すことになります。

大きな問題を、より小さく、同一の形式の問題に分解するというこのアプローチこそが、特定の種類のプログラミングの課題において再帰を非常に強力なものにしている理由です。