Section 6 / 13
再帰の基本とPythonでの実装
再帰は、関数が自分自身を呼び出すことによって問題を解決する手法です。この手法は、特に問題が自己相似的である場合に非常に効果的です。再帰を理解するためには、基本的な構造と、適切に終了条件を設定することが重要です。
再帰の基本構造
再帰関数は、通常以下の2つの部分で構成されています。
- 基本ケース（終了条件）: 再帰を停止する条件です。これがないと、関数は無限に自分自身を呼び続けることになります。
- 再帰的ケース: 問題を小さな部分問題に分割し、再帰的に解決する部分です。
以下に、再帰関数の基本的な構造を示します。
def recursive_function(parameter):
if base_case_condition(parameter):
return base_case_result
else:
return recursive_function(modified_parameter)
再帰を使ったサンプルコード: 階乗の計算
階乗は、自然数 n の階乗を n! と表し、n が 0 または 1 のときは 1、その他の n に対しては n × (n-1)! と定義されます。
以下は、再帰を使用して階乗を計算する Python のコードです。
def factorial(n):
# 基本ケース
if n == 0 or n == 1:
return 1
else:
# 再帰的ケース
return n * factorial(n - 1)
# テスト
print(factorial(5)) # 出力: 120
コード解説
- 基本ケース:
if n == 0 or n == 1:の部分で、n が 0 または 1 の場合、階乗は 1 であるとしています。 - 再帰的ケース:
return n * factorial(n - 1)では、n の階乗を n と (n-1) の階乗の積として計算しています。この関数は、n が 0 または 1 になるまで自分自身を呼び出し続けます。
再帰を使ったサンプルコード: フィボナッチ数列
フィボナッチ数列は、最初の 2 つの数が 0 と 1 で、以降の数は前の 2 つの数の和となる数列です。フィボナッチ数列の n 番目の数は、次のように定義されます。
- fib(0) = 0
- fib(1) = 1
- fib(n) = fib(n-1) + fib(n-2) (n >= 2)
以下は、再帰を使用してフィボナッチ数列の n 番目の数を計算する Python のコードです。
def fibonacci(n):
# 基本ケース
if n == 0:
return 0
elif n == 1:
return 1
else:
# 再帰的ケース
return fibonacci(n - 1) + fibonacci(n - 2)
# テスト
print(fibonacci(6)) # 出力: 8
コード解説
- 基本ケース:
if n == 0:とelif n == 1:の部分で、n が 0 または 1 の場合の結果を返します。 - 再帰的ケース:
return fibonacci(n - 1) + fibonacci(n - 2)では、n 番目のフィボナッチ数を、n-1 番目と n-2 番目のフィボナッチ数の和として計算しています。
再帰の利点と欠点
利点
- 簡潔さ: 再帰を使うことで、コードが短く、読みやすくなることが多い。
- 自然な問題分割: 再帰は自己相似な問題に対して自然なアプローチを提供する。
欠点
- パフォーマンス: 再帰的な計算には、特に重複する計算が多い場合に時間がかかることがある。
- スタックオーバーフロー: 深い再帰は、スタックメモリを消費しすぎて、スタックオーバーフローを引き起こす可能性がある。
まとめ
再帰は、問題を分割して解決する強力な手法です。基本ケースと再帰的ケースを正しく設定することで、さまざまな問題を効率的に解決できます。次のステップとして、再帰的アルゴリズムの応用例について学んでいきましょう。