Python - 再帰: 初心者のガイド

こんにちは、未来のPythonの魔法使いたち！今日、私たちは再帰の魔法の世界に興奮な旅をすることにします。少し恐ろしく聞こえても心配しないでください — 見た目よりも楽しく、理解しやすいようにすることを約束します。だから、お気に入りの飲み物を持って、快適に座って、一緒に飛び込みましょう！

Python - Recursion

再帰とは？

自分と向かい合った鏡の間に立っていると仮定しましょう。無限の反射が見えますよね？それはプログラミングの再帰と少し似ています！簡単に言えば、再帰は関数が自分自身を呼び出して問題を解決することです。

簡単な例から始めましょう：

def countdown(n):
if n <= 0:
print("ブラストオフ！")
else:
print(n)
countdown(n - 1)

countdown(5)

このコードを実行すると、以下のようになります：

5
4
3
2
1
ブラストオフ！

これを分解してみましょう：

countdownという関数を定義し、数値nを受け取ります。
nが0以下の場合、ブラストオフ！と表示します。
それ以外の場合、nを表示し、その後countdownを再度n - 1として呼び出します。

これが再帰の動作です！関数は0に達するまで小さな数で再帰的に呼び出され続けます。

再帰の構成要素

すべての再帰関数には、以下の2つの主要な構成要素があります：

基本ケース：再帰を停止させる条件です。
再帰ケース：関数が自分自身を呼び出す場所です。

私たちのcountdownの例では、以下の通りです：

基本ケースはif n <= 0
再帰ケースはcountdown(n - 1)

別の古典的な例として、階乗を計算するものを見てみましょう。

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

print(factorial(5))  # 出力: 120

以下が起こっていることです：

nが0または1の場合、1を返します（これが基本ケースです）。
それ以外の場合、nをn - 1の階乗で掛けます（これが再帰ケースです）。

したがって、factorial(5)は以下のようになります： 5 factorial(4) 5 (4 factorial(3)) 5 (4 (3 factorial(2))) 5 (4 (3 (2 factorial(1)))) 5 (4 (3 (2 1))) 5 4 3 2 1 = 120

再帰の力

再帰を使うことで、複雑な問題をもっと簡単に解決できるようになります。少し高度な例として、フィボナッチ数列を見てみましょう。

def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)

for i in range(10):
print(fibonacci(i), end=" ")
# 出力: 0 1 1 2 3 5 8 13 21 34

この関数は、n番目のフィボナッチ数を計算します。フィボナッチ数列は0と1から始まり、それぞれの次の数は前の2つの数の和です。

再帰を用いた二分探索

さて、もっと実用的な例として、二分探索を見てみましょう。これは、ソートされたリストでアイテムを見つける効率的な方法です。

def binary_search(arr, low, high, x):
if high >= low:
mid = (high + low) // 2

if arr[mid] == x:
return mid
elif arr[mid] > x:
return binary_search(arr, low, mid - 1, x)
else:
return binary_search(arr, mid + 1, high, x)
else:
return -1

arr = [2, 3, 4, 10, 40]
x = 10

result = binary_search(arr, 0, len(arr)-1, x)

if result != -1:
print(f"要素はインデックス {result} に存在します")
else:
print("要素は配列に存在しません")

この関数は、反復的に検索範囲を半分に分割しています。検索キーの値が範囲の中央のアイテムよりも小さい場合、範囲を下半分に狭めます。それ以外の場合、上半分に狭めます。値が見つかるか、範囲が空になるまで反復的にチェックします。

再帰を使用するタイミング

再帰は特に以下のような場合に便利です：

同じような部分問題に分解できる問題
木構造のデータ構造（例：ファイルシステム、HTML DOM）
QuickSort、MergeSortなどのアルゴリズム

しかし、再帰は常に最良の解決策ではありません。非常に深い再帰ではメモリを使いすぎることがあり、シンプルなループがより効率的で理解しやすい場合もあります。

再帰メソッドの表

メソッド	説明	例
直接再帰	関数が直接自分自身を呼び出す	私たちの`countdown`と`factorial`の例
间接再帰	関数Aが関数Bを呼び出し、関数Bが関数Aを呼び出す	下の例を参照
テール再帰	再帰呼び出しが関数の最後の実行です	私たちの`countdown`の例
非テール再帰	再帰呼び出しが関数の最後の実行ではない	私たちの`factorial`の例

以下は间接再帰の例です：

def is_even(n):
if n == 0:
return True
else:
return is_odd(n - 1)

def is_odd(n):
return not is_even(n)

print(is_even(4))  # 出力: True
print(is_odd(4))   # 出力: False

この例では、is_evenがis_oddを呼び出し、is_oddがis_evenを呼び出します。

結論

おめでとうございます！あなたは驚くべき再帰の世界に初めての一歩を踏み出しました。覚えておいてください、他の強力なツールと同様に、再帰は賢く使用されるべきです。再帰を使うことで、コードがより洗練され、複雑な問題を簡単に解決できるようになりますが、シンプルな問題を不必要に複雑にすることもあります。

Pythonの旅を続ける中で、再帰を適用できる多くの状況に出会うでしょう。続けて練習し、まもなくプロのように再帰を使えるようになります！

Credits: Image by storyset