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

この記事では、再帰関数という特殊な関数の基本的な概念を学び、Pythonを使って最大公約数を求める方法を理解します。

再帰関数を使うことで、簡潔で効率的なコードを書くことができます。

目次から探す

再帰関数とは

再帰関数は、関数内で自分自身を呼び出すことができる関数のことを指します。

Pythonでは、再帰関数を使って簡潔で効率的なコードを書くことができます。

以下に、再帰関数の基本的な構造を示すサンプルコードを示します。

# 再帰的に関数を呼び出すサンプル
def recursive_function(n):
    if n == 0:
        # 0になったら終了
        return 0
    else:
        # 再帰的に関数を呼び出す
        return n + recursive_function(n-1)

result = recursive_function(5) # 5 + 4 + 3 + 2 + 1 + 0
print(result)
15

上記のサンプルコードでは、recursive_functionという再帰関数を定義し、引数nが0になるまで自分自身を呼び出しています。

再帰関数を使う際には、適切な終了条件を設定することが重要です。

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

再帰関数を使用して、2つの整数の最大公約数(Greatest Common Divisor, GCD)を求める方法を説明します。

最大公約数は、2つの整数が共通で割り切れる最大の整数です。

再帰関数を使用することで、簡潔かつ効率的に最大公約数を求めることができます。

以下に、Pythonで再帰関数を使用して最大公約数を求めるサンプルコードを示します。

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

num1 = 36
num2 = 24
result = gcd(num1, num2)
print(f"{num1}と{num2}の最大公約数は{result}です。")
36と24の最大公約数は12です。

このサンプルコードでは、gcdという再帰関数を定義し、2つの整数aとbの最大公約数を求める処理を行っています。

関数内でbが0になるまで、aをbで割った余りを求め、その余りとbの組み合わせで再帰的に最大公約数を求めています。

上記のサンプルコードを実行すると、num1num2の最大公約数が求められ、結果が出力されます。

これで、再帰関数を使用してPythonで最大公約数を求める方法を理解できました。

目次から探す