再帰関数・メモ化再帰のtips

自分がプログラミングの勉強をしていて、再帰関数を自力で実装しようとすると手が進まない場面が多々ありました。

そこで、再帰関数の実装をしやすくすることができた考え方とテンプレートを共有したいと思います。

再帰関数のテンプレート
1. 再帰関数テンプレの具体例: フィボナッチ数列
メモ化再帰のテンプレート
1. メモ化再帰テンプレの具体例: フィボナッチ数列
まとめ

再帰関数のテンプレート

再帰関数の骨組みは以下の通りです。

def rec(引数):
    #1. ベースケース
    if ベースケースの条件:
        return ベースケースに対する値
    
    #2. 再帰関数の呼び出し
    #rec(次の引数)　を用いた計算
    return 答え

このコードに沿って、以下の二点を考えます。

ベースケースの条件は何か?その条件の場合、どの値をreturnすれば良いか?
rec(次の引数) を用いた計算式は何か?

ちなみに、ベースケースは再帰計算せずに値が決まる場合を意味します。

このテンプレートは以下の書籍で紹介されており、このフォーマットに沿って考えることで断然コードを書きやすくなりました。

問題解決力を鍛える！アルゴリズムとデータ構造

競技プログラミング経験が豊富な著者が、「アルゴリズムを自分の道具としたい」という読者に向けて執筆。入門書を標榜しながら、AtCoderの例題、C++のコードが充実。入門書であり実践書でもある、生涯役立

再帰関数テンプレの具体例: フィボナッチ数列

フィボナッチ数列を上記のテンプレートに沿って実装していきたいと思います。

ベースケースは、以下の2点
1. rec(0)=0 ( n = 0)
2. rec(1)=1 ( n = 1)
再帰関数はフィボナッチ数列の一般式. rec(n) = rec( n - 1 ) + rec( n - 2)

以上の考察をもとに、コードを書きます。

def fib(n):
    #1. ベースケース
    if n==0:
        return 0
    elif n==1:
        return 1
    #2. 再帰関数を使った計算式
    else:
        return fib(n-1) + fib(n-2)

これで再帰関数を実装することができました。

メモ化再帰のテンプレート

メモ化再帰は再帰関数の計算を効率化する方法の一つです。

このメモ化再帰も、再帰関数と同じようにテンプレートに沿って実装することが可能です。

memo = [-1]*(n+1)
def rec(n):
    #ベースケース
    if ベースケースの条件:
        return ベースケースに対する値
    
    #メモが初期値でなければ計算せず値を返す
    if memo[n] != 初期値:
        return memo[n]
    
    #再帰関数の呼び出してメモを更新
    memo[n] = rec(次の引数)
    return memo[n]

再帰と異なるのは主に以下の二点です。

初期値を持ったメモを用意し、初期値でなければメモの値を返す(7,8行目)
再帰関数を呼び出してメモの値を更新

メモ化再帰テンプレの具体例: フィボナッチ数列

考えるプロセスは再帰関数の場合とほぼ同じですが、メモのことを考えるプロセスが追加されています。

メモが管理する値は? -> 0以上の整数。よって、初期値は-1に設定すればok
ベースケースは? -> rec(0)=0, rec(1)=1
再帰関数の計算式は? -> 一般式 rec(n) = rec( n - 1 ) + rec( n - 2)

N = int(input())
#1. メモが管理する値は? -> ０以上の整数, 初期値は-1
memo = [-1]*(N+1)
def rec(n):
    #2. ベースケースは?
    if n==0:
        return 0
    if n==1:
        return 1
    #メモの参照
    if memo[n] != -1:
        return memo[n]
    #再帰関数の計算をメモに更新
    memo[n] = rec(n-1)+rec(n-2)
    return memo[n]

ans = rec(N)
print(ans)

ポイントはメモを参照し、-1でない(=更新されている)場合は、その値を返す部分です。(11,12行目)

まとめ

再帰関数を自力で実装するための便利な考え方やテンプレートについてまとめました。自分はこのテンプレートを知り、再帰関数を実装しやすくなったと感じています。

再帰関数で手こずっている方の助けになれば幸いです。

今回のメモ化再帰コードはアルゴ式で全問正解になることを確認済みです。

フィボナッチ数列 (再帰-2) | アルゴ式(beta)

また、部分和問題をメモ化再帰で解く方法について以下のサイトで解説しています。正解コードだけでなく、自分の失敗コードのダメな部分の考察もあるので、ご興味があればご覧ください。

以下の書籍を参考にしたので、興味があればご覧ください。

問題解決力を鍛える！アルゴリズムとデータ構造