Python : 再帰は大きな問題が小さな問題に収束するように使う

• 作成：2022/01/14
• 更新：2022/12/09
• Python > 組み込み関数

関数の再帰呼び出しとは「関数 A の中から、この関数 A 自身を呼び出すこと」である。

「ある手続きを実行している最中に、同じ手続きを、違う対象について行う」といった入れ子構造になった処理。大きな問題が小さな問題に収束するように使う。

エンジニア速報は Twitter の@commteで配信しています。

再帰のルール

1. 再帰終了条件を持つ
2. 状態を変更しながら再帰終了条件に進む
3. 再帰的に関数自身を呼び出す

再帰関数の定義は 2 つある。

1 つ目は終了条件。終了条件は、最小の問題を処理する箇所。再帰呼び出しをせずに直接的に値を返す。2 つ目は再帰条件。再帰条件は「より小さな問題」を処理するための再帰呼び出しを行う。

問題を小さく分解していけば最終的に最小の問題を経由し終了条件が満たされるので、再帰が終了する。

関数は呼び出されるたびに新しい名前空間を作るが、自分自身を呼び出したときも別の名前空間をもった同じ関数が実行される。

東京大学 再帰によると、再帰関数による分割統治の典型的な形は、次のように書かれている。

def recursive_function(...):
    if 問題粒度の判定:
        再帰呼び出しを含まない基本処理
    else:
        再帰呼び出しを含む処理（問題の分割や部分解の合成を行う）

次は再帰処理のシンプルな例である。引数 n を減算した値を、関数 total で加算しながらループさせ、n が 0 までたどり着いたときに再帰を停止する。

"""1からn（引数）までの合計値

n = 10 のとき:
    10 + sum(10-1)

n = 9 のとき:
    9 + sum(9-1)

n = 0 のとき:
    return 0
"""

def total(n):
    if n < 1: # 0 の時、再帰を停止
        return 0
    return n + total(n - 1) # 引数を減らしていく

print(total(3))
# 6
# 3 + 2 + 1

階乗の計算（何通りの組み合わせがあるか？）を計算する例。引数に渡された数値を -1 しながら乗算している。

def fac(n):
    if n == 1:
        return 1
    else:
        return n * fac(n - 1)

print(fac(3))
# 6
# 3 * 2 * 1 = 6

入門 Python 3より。リストのリストなど入れ子になったデータを平坦化するコード。

def flat(x):
    for i in x:
        if isinstance(i, list):
            for i_in in flat(i):
                yield i_in
        else:
            yield i

x = [1, 2, [3, 4, 5], [6, [7, 8, 9]]]
list(flat(x))

# [1, 2, 3, 4, 5, 6, 7, 8, 9]

入力の文字列の接頭辞リストを返す関数 prefixes

def prefixes(s):
    if s == '':
        return []
    else:
        return [s] + prefixes(s[:-1])

a = prefixes('aabcc')
print(a)
# ['aabcc', 'aabc', 'aab', 'aa', 'a']

# 入力の文字列の接尾辞リストを返す関数suffixes
def suffixes(s):
    if s == '':
        return []
    else:
        return [s] + suffixes(s[1:])

suffixes('aabcc')
# ['aabcc', 'abcc', 'bcc', 'cc', 'c']

べき乗の計算を繰り返し処理で行った例

def power(base, expt):
    e = 1
    for i in range(expt):
        e *= base
    return e

a = power(2,3)
print(a)
# 8

フィボナッチ数列は、１、１、２、３、５、８、１３、２１、３４、５５、８９、１４４、２３３のように「どの数字も前２つの数字を足した数字」という規則の数列である。

def fib(n):
    if n < 2:
        return n
    else:
        return fib(n-1) + fib(n-2)

print(fib(10))
# 55

Python おすすめ本

• Python実践入門
• エキスパートPythonプログラミング 改訂3版
• 入門 Python 3 第2版
• Pythonハッカーガイドブック
• Effective Python 第2版