【ユーザー定義関数def】再帰関数

　関数の中でその関数自身を呼び出すものを再帰関数という。これにより類似の処理を繰り返すことができる。

目次

---

1. nまでの合計を求める
2. 最大公約数を求める(ユークリッドの互除法)

1. nまでの合計を求める

　再帰関数を作成する上で必要な点は以下3つ。
　①　return文でその関数自身を呼び出す
　②　終了条件が決められておりそれを満たすと関数を抜ける
　③　return文でその関数自身を呼び出す際、終了条件に近づける
①により再帰処理が実行される。②③があることでループから抜け出せる(②③が無いと無限ループとなる)。

1からnまでの整数の和を求める関数sumを定義する例。上記の条件については
　①　return文で関数sumそれ自身を呼び出している
　②　nが0以下の場合nを返して関数から抜け出す
　③　return文でsum(n-1)として引数を小さくし終了条件であるn <= 0に近づく
となる。
　n=10として関数sumを呼び出すと戻り値は 10+9+ … +1+0 となり1から10までの数の合計が求まる。

def sum(n):
    # 終了条件。nが0以下となったら関数を抜ける
    if n <= 0:
        return n
    # 自身を呼び出す。その際n-1としてnが0に近づくようにする
    return n + sum(n-1)

print(sum(10))

実行結果

55

2. 最大公約数を求める(ユークリッドの互除法)

　ユークリッドの互除法は2つの自然数 a, b の最大公約数を求める手法で、「aをbで割った余りをrとした場合、a, b の最大公約数はb, rの最大公約数に等しい」という性質を利用している。再帰関数で求めるにはb, rを新たなa, bとして余りを求める。この計算を余りが0になるまで繰り返せばよい。
40と16の最大公約数を求める場合。終了条件として40/16の余りは8。引数16と8で再び関数gcdを呼び出す。16/8の余りは0なので8を戻り値として関数を終了。

def gcd(a, b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)
    
print(gcd(40, 16))

実行結果

8

　188と152の最大公約数を求める場合。188%152=36、152%36=8、36%8=4、8%4=0となり4を戻り値として関数を抜ける。

def gcd(a, b):
    r = a % b
    if r == 0:
        return b
    else:
        return gcd(b, r)
    
print(gcd(188, 152))

実行結果

4

使用バージョン:Python 3.8.8

---