再帰関数の応用例
再帰関数は単純なアルゴリズムだけでなく、より高度な問題にも応用可能です。再帰を利用することで、複雑な問題を小さな問題に分割して解決することができます。本記事では、いくつかの実践的な再帰関数の応用例を紹介します。
応用例 1: フィボナッチ数列
フィボナッチ数列は、最初の2つの項が1で、以降の項は前の2つの項の和で定義される数列です。再帰関数を使ってフィボナッチ数列を計算することができます。
# フィボナッチ数列を再帰で計算
def fibonacci(n):
if n <= 1:
return n
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10)) # 出力: 55
この関数は、n
が0または1の場合はそのまま返し、それ以外の場合は、前の2つの項を再帰的に計算してその和を返します。ただし、再帰的な計算には冗長な計算が含まれるため、大きな数値に対しては効率が良くありません。
応用例 2: ユークリッドの互除法
再帰は、最大公約数(GCD: Greatest Common Divisor)を求めるための「ユークリッドの互除法」でも活用されます。このアルゴリズムは、2つの整数の最大公約数を求める効率的な方法です。
# 再帰を使ったユークリッドの互除法
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
print(gcd(48, 18)) # 出力: 6
ユークリッドの互除法では、整数a
とb
の最大公約数は、b
が0になるまでa % b
を計算し続け、その時点のa
を返します。
応用例 3: ハノイの塔
ハノイの塔は、再帰を使って解く有名なパズルです。3本の柱と異なるサイズのディスクがあり、1本の柱からすべてのディスクを別の柱に移動する必要があります。ただし、1度に1つのディスクしか動かせず、かつ大きなディスクを小さなディスクの上に置くことはできません。
# ハノイの塔を再帰で解く
def hanoi(n, source, target, auxiliary):
if n == 1:
print(f"{source}から{target}へディスクを移動")
else:
hanoi(n - 1, source, auxiliary, target)
print(f"{source}から{target}へディスクを移動")
hanoi(n - 1, auxiliary, target, source)
hanoi(3, 'A', 'C', 'B')
この例では、n
枚のディスクをA
柱からC
柱に移動させる手順を再帰的に計算しています。再帰を使うことで、複雑な問題を簡単に解くことができることが分かります。
再帰関数のメリットとデメリット
メリット | デメリット |
---|---|
再帰的な問題をシンプルに解くことができる。 | 効率が悪くなる場合がある(特に冗長な再帰計算)。 |
コードが直感的で読みやすくなる。 | 再帰の深さが大きいとメモリを多く消費する。 |
まとめ
再帰関数は、フィボナッチ数列やユークリッドの互除法、ハノイの塔など、さまざまな場面で応用されます。再帰を使うことで、複雑な問題を簡潔に解くことができる一方、計算の効率やメモリ消費には注意が必要です。適切に使用することで、再帰関数は非常に強力なツールとなります。