再帰
プログラミングを学ぶとき、私たちはしばしば直線的で単純な方法でタスクに取り組みます。しかし、もし問題をより小さく、似たような問題に分解する必要がある場合はどうでしょうか？そこで再帰が役立ちます。
簡単に言うと、再帰とは、関数が実行中に自分自身を呼び出すことです。これは無限ループを引き起こすように思えるかもしれませんが、関数を正しく設計すれば、最終的には自分自身を呼び出さなくなるポイントに到達します。
マトリョーシカ人形を想像してください。人形を開くたびに、その中により小さな人形があり、開け続けると、開けられない最小の人形にたどり着きます。この人形を開ける過程は再帰に似ています。最小の人形にたどり着くには、同じ問題のより簡単なバージョンを繰り返し解く（大きな人形を開ける）ことで、これ以上問題を縮小できないポイント（最後の人形）に到達します。
大きな問題を再帰的により小さな問題に分割して、可能な限り最小・最も簡単なものに到達するまで解決するプロセスは、「再帰的な信念の飛躍」という概念で最もよく理解できます。
再帰的な信念の飛躍
問題に対する再帰的な解決策を実装する際、通常はある時点で自分自身を呼び出す関数を作成します。この自分自身を呼び出す部分は、一般的に再帰呼び出しと呼ばれます。
再帰的な解決策の素晴らしい点は、単純な引数で呼び出されたときに関数が正しく動作すると仮定し、より複雑な場合に対して正しい動作を実装できることです。これまで使用してきた
sqrt、max、abs などの他の関数を呼び出すのと同様に、関数がより小さく単純な引数で動作することを仮定し、それらを呼び出して現在の結果を構築できます。💡
唯一の要件は、関数がベースケース（最も単純なケース）に到達することを確実にすることです。さもないと、関数は無限に再帰し、スタックオーバーフロー を起こす可能性があります！
再帰関数内での計算がどのように行われるかを示すために、数値
n が与えられたときに 0, 1, 2, …, n のすべての数の合計を計算してみましょう。sum 関数をステップごとに実装してみましょう。最初のステップは、関数が最も単純なケース（n が 0 または 1）の場合に正しく動作することを確認することです。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0: # n が 0 の場合 => 合計は 0
return 0 # ここで関数の実行を停止する
if n == 1: # n が 1 の場合 => 合計は 1
return 1 # ここで関数の実行を停止する
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> None (まだこの部分を実装していないため)この部分の関数があれば、
sum(0) は常に正しく 0 を返し、sum(1) は常に 1 を返すことを利用できます。関数内で引数 0 または 1 で sum 関数を呼び出しても、関数は正しく動作します。そこで、
sum(1) と sum(0) の結果を利用して、n = 2 と n = 3 の場合の sum 関数をさらに一歩進めて実装できます。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2: # n が 2 の場合、sum(1) の結果に 2 を加えることができる
return n + sum(1) # または n + sum(n - 1)
if n == 3: # n が 3 の場合、sum(2) の結果に 3 を加えることができる
return n + sum(2) # または n + sum(n - 1)
print(sum(1)) # sum(1) -> 1
print(sum(0)) # sum(0) -> 0
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> None (まだこの部分を実装していないため)このようにして、
n が 0、1、2、3 のような小さなケースで sum 関数が正しく動作することが明らかです。これを踏まえて、
n が 3 より大きい他の値の場合でも関数を実装できます。唯一の要件は、sum 関数を再帰的に呼び出す際に、より小さな n の値（0、1、2、または 3）に到達することです。したがって、n が 4、5、6 などのより大きな値の場合、sum(4) を計算するには sum(3) の結果に 4 を加えることで、sum(5) を計算するには sum(4) の結果に 5 を加えることで、sum 関数を実装できます。def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
if n == 1:
return 1
if n == 2:
return n + sum(1)
if n == 3:
return n + sum(2)
# その他のケース（4、5、6、...）の場合
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...再帰関数の重要な部分は次の通りです：
- ベースケース: 再帰を停止させる条件。これがないと、関数は無限に自分自身を呼び出し、無限ループを引き起こします。
ここでは、
n == 0とn == 1です。
- 再帰ステップ: 関数が自分自身を呼び出す部分。通常は異なる引数で呼び出します。
ここでは、
sum(n - 1)です。
n == 1、n == 2、n == 3 の呼び出しは、n == 4、n == 5 などの場合とまったく同じなので、n == 0 の1つのベースケースだけを持つことで sum 関数をさらに簡略化できます：def sum(n):
print(f'sum({n})', end=' -> ')
if n == 0:
return 0
return n + sum(n - 1)
print(sum(2)) # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3)) # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4)) # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...このようにして、再帰的な信念の飛躍を持ち、関数がより小さく単純なケースで正しく動作すると仮定・確信し、それらの単純なケースに基づいて関数の残りを構築します。これにより、再帰関数がどのように動作し、どのように実装できるかを理解するのに役立ちます。
💡
関数を再帰的に呼び出すことは、渡された引数で確実に動作することを知っている全く別の関数を呼び出すようなものです。