今回は再帰関数についての記事です。

普段は使う機会があまりないんですが、プログラミングコンテストなどで問題として挙げられることもあり。

覚えておくと、どこかで使えるかもしれません。ということで、簡単にまとめてみました。

再帰関数とは

自身で呼び出しを行う関数のことです。

実装例で有名なところだと階乗を行うような計算でしょうか。

4という数字が与えられたら、4x3x2x1とするようなケースです。

まずは通常の書き方をするとこうなると思います。

def factorial(n: int) -> int:
    the_product = 1
    while n > 0:
        the_product *= n
        n = n - 1
    return the_product


print(factorial(4))
>>>
24

これを再帰関数で書き換えるとこうなります。

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


print(factorial(4))
>>>
24

かなり短くなりました。

return 文のところで自身を呼び出しているのが特徴です。

引数は元々受け取った数から、１を引いています。

そうして呼び出し続けていくと、最終的に引数が0になるまで続きます。

# 1回目
4 * 3
# 2回目
4 * 3 * 2
# 3回目
4 * 3 * 2 * 1
# 4回目
# ここで収束
4 * 3 * 2 * 1 * 1

再帰の条件

まとめると、以下のような条件を持つことが再帰関数の特徴です。

• 終了条件を持つ
• 毎回状態を変え、終了条件に近づく
• それ自身を再帰的に呼び出す

上の例ですと、n==0のときが終了条件ですね。

最初に受け取った引数から１を引いて呼び出す部分が終了条件に近づく、といったところでしょうか。

再帰のメリット

以上の比較のように非常にコードが簡素化されるところにメリットがあります。

あと、使ってるとかっこいい、ってのはあると思います。

再帰のデメリット

デメリットとしては、コードの処理が追いづらくなる点でしょうか。

コードは長いものの、whileループの方が分かりやすいです。

乱用すると思わぬバグに出くわす危険があるかもしれません。

メモによる再帰の高速化

再帰は普通に計算を行うと無駄な計算をしてしまう場合があります。

例えば先ほどの階乗関数に手を加えて以下のようにしてみましょう。

def double_factorial(n):
    if n == 0:
        return 1
    return n * double_factorial(n - 1) + n * double_factorial(n - 1)

a = double_factorial(2)
print(a)
>>>
8

何が起きているか分かりませんが、一応処理を追ってみましょう。

この関数をfとします。

# 1回目
2 * f(1) + 2 * f(1)
# 2回目
2 * 1 * ( f(0) + f(0) ) + 2 * 1 * ( f(0) + f(0) )
# 3回目
2 * 1 * (1 + 1) + 2 * 1 * ( 1 + 1 )

引数が３以上になるとちょっと追うのが難しいですが、２の場合は上のような流れでしょうか。

ここで分かる通り、同じような計算をしていることが分かります。

このくらいの数だったらいいんですが、数が増えれば増えるほど指数関数的に計算量が増えていきます。

なので、一度おこなった計算を記録するメモを用意する…というのが高速化の秘訣らしいです。

def double_factorial(n, _memo):
    # 答えが記録済みだったら、再計算はせず返す
    if n in _memo:
        return _memo[n]
    # 答えがない場合は再帰的に計算する
    if n == 0:
        ret = 1
    else:
        ret = n * double_factorial(n - 1, _memo) + n * double_factorial(n - 1, _memo)

    # 答えを記録する
    _memo[n] = ret
    # 値を返す
    return ret

または組み込みに便利な機能がありまして、次のように書くと同様にメモ化再帰が行えるようです。

from functools import lru_cache


@lru_cache(maxsize=None)
def double_factorial(n):
    if n == 0:
        return 1
    return n * double_factorial(n - 1) + n * double_factorial(n - 1)