再帰関数（python）

サバくん

木構造や漸化式を表現するときに便利なのが再帰関数。

難しく感じる人が多いと思いますが、使えると便利ですよ！！

再帰関数とは

再帰関数とは関数内にその関数が呼び出されている関数です。文字だけで説明するとよくわからないと思うので図で見てみましょう。再帰関数のイメージは数珠つなぎ構造の場合と木構造の場合で2つに分けて理解するとわかりやすいです。イメージは以下の通り。

どちらも関数がつながっていく様子がわかると思います。

数珠つなぎ構造の再帰関数

数珠つなぎの構造は入力値がその関数に入力される構造です。一番簡単な構造なので理解しやすいかもしれません。

例えば上の図のように関数が並んでいて、左からfunc1, func2, func3, func4, func5と5つの関数が並んでいるとします。（それぞれの関数は全て同じ処理を行う関数で入力値をprintで出力して、引数から1引いた数を返します。）これをコード化すると以下のようになります。

# 関数を作成する。
def func1(a):
    print(a)
    return a-1

def func2(a):
    print(a)
    return a-1

def func3(a):
    print(a)
    return a-1

def func4(a):
    print(a)
    return a-1

def func5(a):
    print(a)
    return a-1

# 一番最初の（func1に入力する）引数を5にすると、、
a = 5
func5(func4(func3(func2(func1(a)))))

# 出力
# 5
# 4
# 3
# 2
# 1
# [返り値] 0

コードをみてみると、同じ処理を行うコードが何箇所もあり、長い、めんどくさいですね、パソコンは繰り返しの処理や同じ処理が得意なのにこのコードはスマートではありません、、

また、今回は関数の数が5つわかっていましたが、数がわからなかったり、必要な数が変化するととても対応することができません。

func1, func2, func3, func4, func5は全て同じ処理なので、funcでまとめてしまいましょう。

def func(a):
    print(a)    
    return func(a-1) # 次の関数に渡すように返り値を設定する。
func(5)

かなりスッキリしましたね。しかしこのコードを実行すると、多量の数値の出力と

RecursionError: maximum recursion depth exceeded while calling a Python object

というエラーが出ます。上の処理だとどこで処理を終えて良いのかがわからないので終了条件を加えましょう！！（終了条件はaが0以下になったとき）

def func(a):
    print(a)
    
    # 終了条件
    if a <= 0:
        return None
    
    return func(a-1)

func(5)
# 出力
# 5
# 4
# 3
# 2
# 1
# 0

このように再帰関数を作成するときには作成している関数内に作成している関数名を入れます。

再帰関数を用いると「1〜nまでの和」のような処理も簡単に記述することができます。

イメージは以下の通り。

def sum_one2n(n):
    # 終了条件
    if n <= 0:
        return 0
    return n + sum_one2n(n-1)

sum_one2n(5)
# [Out] 15

このようなテクニックを使用すると漸化式なども綺麗に記述できます。

木構造

再帰関数は木構造の処理を行うときにも便利です。

例えば、深さのあるリスト構造[[[1, 2], [3, 4]], [[5, 6], [7, 8], [9, 10]]]があり、これらの要素を順にprintで出力したいとします。

要素を順にprintで出力するコードを再帰関数を用いないで記述すると以下のようになります。

lis = [[[1, 2], [3, 4]], [[5, 6], [7, 8], [9, 10]]]
for i0 in lis:
    for i1 in i0:
        for i2 in i1:
            print(i2)

for文がとてもたくさんありますね、、今回は３階層の木構造であるとわかっていたので記述できましたが、木構造の深さがわからない時はいちいち調べてから記述しないといけいないなど、面倒でとても対応できません。

再帰関数を用いて記述すると以下のようになります。

def list_print(lis):
    if isinstance(lis, list):
        for i in lis:
            list_print(i)
    else:
        print(lis)
    return None
list_print(lis)

lis = [[[1, 2], [3, 4]], [[5, 6], [7, 8], [9, 10]]]
list_print(lis)

引数に入力された値はリスト型であれば（深さがあれば）for文に入力され、要素ごとに再び関数に入力されます。そうでなければ（それ以上深さがなければ）、値をprintで出力します。

これを繰り返すことで木構造を表現することができます。上で説明した数珠つなぎ構造と違うのはif文とfor文が組み合わさっているところですかね。

練習

再帰関数を用いて入力したn（自然数）の階乗（1〜nの掛け算）を求める関数を作成しよう

def factorial(n):
    if n==0:
        return 1
    return n * sum(n-1)

def list_flatten(lis, new_lis=[]):
    if isinstance(lis, list):
        for i1 in lis:
            list_flatten(i1, new_lis)
    else:
        new_lis.append(lis)
    return new_lis

lis=[[[1], [2, 3, [4, [5, [6]], 7], 8, [[[9]]], 10], 11], [12, 13], [14, [[15]]], 16, [17, [18, 19], 20]]
list_flatten(lis, new_lis=[])

まとめ

今回は再帰関数について記述しました。少し難しかったかもしれません。（その場合は僕の説明が悪かったので分かりにくかったところを教えてください。）再帰関数は使えるとコードがすっきりして良いので是非使ってください。

脱Python初心者ロードマップ