再帰関数を用いた問題解決技法（メモ化、分割統治法）

種々のアルゴリズムで出くわすことになる再帰関数と、メモ化による高速化、分割統治法への適用を、簡単な問題解決事例でまとめました。

再帰関数

再帰関数とは、手続きの中で自分自身を呼び出す（＝再帰呼び出しを行う）関数のことです。

Fibonacci-recursive.py

# フィボナッチ数列を求める再帰関数
# 計算量：O((1+√5/2)^N)
def fibo(N):
    if N == 0:
        return 0
    elif N == 1:
        return 1

    return fibo(N-1) + fibo(N-2)

# 入力受取
# 求めるフィボナッチ数列の番号
digits = int(input())

# 再帰的に解く
fibo(digits)

# 入力 40
# 出力 102334155

メモ化による高速化

メモ化とは、計算済みの部分問題の解をメモしておき、再帰関数の中で同じ部分問題に２度目以降出くわした際はメモから解を取得し、部分問題が計算し直されるのを防ぐ手法です。

Fibonacci-memo.py

# フィボナッチ数列を求める再帰関数メモ化
# 計算量：O(N)
def fibo(N):
    if N == 0:
        return 0
    elif N == 1:
        return 1

    if memo[N] != -1:
        return memo[N]
    else:
        memo[N] = fibo(N-1) + fibo(N-2)
        return memo[N]

# 入力受取
# 求めるフィボナッチ数列の番号
digits = int(input())

# メモ準備
# フィボナッチ数10000番目分までのメモを-1で初期化
memo = [-1 for number in range(0,10000)]

# メモ化で解く
fibo(digits)

# 入力 100
# 出力 354224848179261915075

ちなみに大きな桁数のフィボナッチ数列は単純なfor文でも解けます。
再帰関数を使えるようになるとついついfor文を侮ってしまいますが、いけませんね。

Fibonacci-for.py

# フィボナッチ数列を求めるFor文
# 計算量：O(N)
def fibo(N):
    F = []
    F.append(0)
    F.append(1)
    for i in range(2, N+1):
        F.append(F[i-1]+F[i-2])
    return F[-1]

# 入力受取
# 求めるフィボナッチ数列の番号
digits = int(input())

# for文で解く
fibo(digits)

# 入力 100
# 出力 354224848179261915075

分割統治法への適用

分割統治法とは、元の問題を小さな部分問題に分解し、その部分問題の解を組み合わせることで元の問題の解を求める手法です。

SubsetSum-recursive.py

# 部分和問題を再帰関数を用いる全探索で解く
# 計算量（O(2^N))
def func(i, w, a):
    if i == 0:
        if w == 0:
            return True
        else:
            return False

    if func(i-1, w ,a):
        return True

    if func(i-1, w-a[i-1], a):
        return True

    return False

# 入力受取
# 整数の数、求める総和
N, W = map(int, input().split())

# 入力受取
# N個の整数
a = list(map(int, input().split()))

# 再帰的に解く
if func(N, W, a):
    print("Yes")
else:
    print("No")

# 入力
# 4 7
# 2 3 6 0

# 出力
# No