[Python] 再帰関数で最大公約数を求める方法

Pythonでは、再帰関数を用いて最大公約数を求めることができます。最大公約数を求める一般的な方法として、ユークリッドの互除法があります。

この方法では、2つの整数の最大公約数を求めるために、整数のうち小さい方で大きい方を割った余りを次の計算に用います。

再帰関数を使うことで、余りが0になるまでこのプロセスを繰り返し、最終的に最大公約数を得ることができます。

Pythonでは、関数を定義し、その中で再帰的に呼び出すことでこのアルゴリズムを実装できます。

Pythonで再帰関数を使った最大公約数の実装

Pythonでの再帰関数の基本的な書き方

再帰関数とは、関数が自分自身を呼び出すことで問題を解決する手法です。

Pythonでは、再帰関数を定義する際に、基本的な構造として以下の要素が必要です。

• 基底条件: 再帰を終了させる条件を設定します。

これがないと無限ループに陥る可能性があります。

• 再帰呼び出し: 問題を小さくして自分自身を呼び出します。

以下は、再帰関数の基本的な例です。

def factorial(n):
    # 基底条件: nが0の場合、1を返す
    if n == 0:
        return 1
    # 再帰呼び出し: n * (n-1)の階乗を計算
    return n * factorial(n - 1)
# 例: 5の階乗を計算
print(factorial(5))

このコードは、与えられた整数の階乗を計算します。

factorial関数は、自分自身を呼び出すことで、nが0になるまで計算を続けます。

再帰関数を用いた最大公約数の実装例

最大公約数(GCD: Greatest Common Divisor)を求めるための再帰関数の実装は、ユークリッドの互除法を利用します。

この方法は、2つの整数の最大公約数を効率的に求めることができます。

以下は、再帰関数を用いた最大公約数の実装例です。

def gcd(a, b):
    # 基底条件: bが0の場合、aを返す
    if b == 0:
        return a
    # 再帰呼び出し: bとaをbで割った余りの最大公約数を計算
    return gcd(b, a % b)
# 例: 48と18の最大公約数を計算
print(gcd(48, 18))

このコードは、2つの整数aとbの最大公約数を求めます。

gcd関数は、bが0になるまで再帰的に自分自身を呼び出し、最終的に最大公約数を返します。

6

この実行例では、48と18の最大公約数が6であることを示しています。

ユークリッドの互除法により、効率的に計算が行われています。

応用例

再帰関数を用いた最小公倍数の計算

最小公倍数(LCM: Least Common Multiple)は、2つの整数の倍数の中で最小の共通のものを指します。

最大公約数(GCD)を利用して、最小公倍数を効率的に計算することができます。

以下の例では、再帰関数を用いて最小公倍数を求めます。

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)
def lcm(a, b):
    # 最小公倍数の計算: aとbの積を最大公約数で割る
    return abs(a * b) // gcd(a, b)
# 例: 12と18の最小公倍数を計算
print(lcm(12, 18))

36

この実行例では、12と18の最小公倍数が36であることを示しています。

最大公約数を利用することで、効率的に計算が行われています。

再帰関数を用いたフィボナッチ数列の計算

フィボナッチ数列は、最初の2つの数が0と1であり、その後の数が直前の2つの数の和である数列です。

再帰関数を用いて、フィボナッチ数列のn番目の数を計算することができます。

def fibonacci(n):
    # 基底条件: nが0または1の場合、nを返す
    if n <= 1:
        return n
    # 再帰呼び出し: n-1番目とn-2番目のフィボナッチ数を足す
    return fibonacci(n - 1) + fibonacci(n - 2)
# 例: フィボナッチ数列の10番目の数を計算
print(fibonacci(10))

55

この実行例では、フィボナッチ数列の10番目の数が55であることを示しています。

再帰的に計算することで、フィボナッチ数列を簡潔に表現できます。

再帰関数を用いたハノイの塔の解法

ハノイの塔は、異なるサイズの円盤を3本の棒に移動させるパズルです。

再帰関数を用いることで、円盤を移動させる手順を効率的に求めることができます。

def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n - 1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n - 1, auxiliary, target, source)
# 例: 3枚の円盤をAからCに移動
hanoi(3, 'A', 'C', 'B')

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

この実行例では、3枚の円盤をAからCに移動する手順が示されています。

再帰的なアプローチにより、複雑な移動手順を簡潔に表現できます。

よくある質問

まとめ

再帰関数は、問題を分割して解決する強力な手法であり、特に木構造や分割統治法に関連する問題で有効です。

再帰関数とループの違いや、再帰関数を使うべき場面、パフォーマンスの改善方法について理解することで、より効率的なプログラムを作成できます。

この記事を参考に、再帰関数を活用して、さまざまなアルゴリズムや問題解決に挑戦してみてください。