プログラミング初心者が学ぶ「再帰」

はじめに

前回の記事で、抽象化というプログラミングの基本的な概念を説明しました。
プログラミング初心者が学ぶ「抽象化」

今回は「再帰」について学びます。「再帰」を理解するために自分なりにまとめてみようと思います。私自身まだ学習途中なので、何か間違いがあるかもしれません。もしご指摘やアドバイスがありましたら、ぜひコメント欄からお知らせください。
プログラミングにおいて、再帰は非常に重要な概念で、繰り返しを必要とする処理を簡潔に記述するために使用されます。

再帰とは

再帰とは、あるプロセスが自分自身を参照、または自分自身を含む振る舞いを示すことを指します。この概念は、自然科学、数学、芸術、哲学、そしてコンピュータサイエンスなど、多くの分野で利用されます。

マトリョーシカ人形を思い浮かべてみてください。最初の大きな人形を開けると、その中にさらに小さな同じ形の人形が入っています。それを開けると、さらに小さな人形が出てきます。この繰り返しを最後の最小の人形に辿り着くまで続けます。ここで、大きな人形から最小の人形へと進むこのプロセスが再帰の一例と言えます。

プログラミングで使わる再帰は、再帰関数、再帰プログラミングと呼ばれています。再帰関数とは、ある関数において自分自身を再度呼び出す関数のことを指します。一見難しく思えるかもしれませんが適切に利用すると、複雑な問題を簡単に解決することができます。
　
簡単な例を挙げると、階乗の計算があります。

Pythonで「5の階乗」を記述すると

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

print(factorial(5))  # Output: 120

「5の階乗」は「5と、4の階乗の掛け算」、「4の階乗」は「4と、3の階乗の掛け算」…という風に、関数が自身を呼び出すことで計算が進行していきます。。最終的には、「1の階乗」が1と定義されているので、計算はそこで止まり、全ての掛け算の結果を返します。
このコードでは、factorial(5)は5 * factorial(4)と処理され、これはさらに5 * (4 * factorial(3))と処理されます。このプロセスはnが1になるまで続きます。そのため、factorial(5)は最終的に5 * 4 * 3 * 2 * 1と評価され、その結果は120になります。このように、自分自身を再び呼び出す関数を再帰関数と呼びます。

再帰関数を理解するためには、主に2つの重要な構成要素を理解する必要があります。

• ベースケース：ループが終了する条件。つまり、再帰呼び出しを止める条件です。これがないと、関数は無限に自身を呼び続け、プログラムは無限ループに陥ってしまいます。

• 再帰ケース：ベースケースに到達するまで、関数が自身を呼び出す部分です。

先ほどの関数で考えると、

#ベースケース　この部分がないと無限に関数が呼び出される。
if n == 1: 
    return 1

#再帰ケース　自分自身を呼び出す。
else: 
    return n * factorial(n-1)

再帰のデメリット

再帰には多くのメリットがある一方で、デメリットも存在します。

デメリット

• 関数が自分自身を深く呼び出す場合、コンピュータのメモリが不足する可能性があります。これを「スタックオーバーフロー」と呼びます。
• 非再帰的なプログラムに比べて、再帰は計算リソース（時間やメモリ）を多く消費する可能性があります。

まとめ

再帰はプログラミングの基本的な概念であり、その使用方法を理解することは非常に重要です。再帰を適切に用いると、難しい問題をシンプルに表現することができ、コードが整理され、読みやすくなります。

しかし、扱いに注意する必要があります。適切なベースケースを設定しなければ、関数が永遠に自分自身を呼び出し続け、プログラムが停止しなくなる「無限ループ」に陥る可能性があります。

また、再帰関数が深く自身を呼び出す場合は、コンピュータのメモリを大量に消費し、パフォーマンスに影響を与える可能性があります。そのため、再帰を使用する際には、その効果と限界を理解し、適切なケースで使用することが求められます。また、再帰の深さを理解し、不要な深さを避けることも重要です。