Pythonでの再帰関数とメモ化

python3での再帰関数とメモ化についてまとめました．

はじめに
例１：階乗
例２：ユークリッドの互除法を用いた最大公約数
本題：フィボナッチ数列

はじめに

再帰関数とは．
定義の中に，自分自身を呼び出す（再帰）ようにして定義される関数のことです．
今回例にあげる再帰関数は，引数nが定数で明らかにn回以下のの繰り返しで書き換えることが可能なものばかりですが，再帰を用いて定義することにより簡単に記述することができます．

再帰関数はシンプルに実装すると，同じ計算を何回もすることが多いので，計算量の無駄が多くなります．
無駄を減らすためにいくつかの方策があるようなので，調べてまとめてみました．

例１：階乗

階乗とは，
$n! = n * (n-1) * \cdots *2 * 1$
の計算のことです．階段のように一段ずつ変化する数をかけていくのでこう呼ばれています．
これを素直に実装すると，

 #階乗
def easyFact(n):
    if ( n==0 ): 
        return 1
    else: 
        return n*easyFact(n-1)

#結果
print([easyFact(i) for i in range(10)])

となります．

結果は

[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

例２：ユークリッドの互除法を用いた最大公約数

#最大公約数
def gcd(a,b):
    if ( b==0 ):
        return a
    else:
        return (gcd(b, a%b))

#結果
print(gcd(456,276))

結果は

本題：フィボナッチ数列

本題のフィボナッチ数列です．
フィボナッチ数列は，
1 1 2 3 5 8 13......
と，前２つの数を足していくことでつくられる数列です．少し前にダヴィンチ・コードなどで取り上げられて一躍有名になりました．

単純

#単純な再帰
def simFib(n):
    if ( n<=1 ):
        return 1
    else:
        return simFib(n-2) + simFib(n-1)

フィボナッチ数列のルールとして，初項は1，第2項は(0+1)で1が予め決まっています．
第3項以降は上であげた漸化式 $a_{n+2} = a_{n+1}+a_n$ に沿って計算していきます．
この例ではnを更新するたびにわざわざ初項から計算しなおすことになり，実行速度が大変遅くなります．

末尾再帰

高速化には以下のような方針があります．

def endFib(n, a1 = 1, a2 = 0):
    if (n < 1): 
        return a1
    else:
        return endFib(n-1, a1 + a2, a1)

直前の2つの値をa1，a2に記憶しておけば計算量が減るという考え方です．

繰り返し

def repFib(n):
    a1, a2 = 1, 0
    while n > 0:
        a1, a2 = a1 + a2, a1
        n -= 1
    return a1

末尾再帰は繰り返しに書き換えることができます．

行列

import numpy as np
def matFib(n):
    m = np.matrix('1 1 ; 1 0') ** n
    return m.item(0)

あくまでフィボナッチ数列に限った話ですが，この数列は行列をn乗した行列の要素として表現できます．
よって計算量はO(n)となります．

メモ化

本命です．
実はmemoFib()の動作はsimFib()と全く同じですが，メモ化関数memoize()を定義し，デコレータ表記を用いてメモ化しています．

def memoize(f): #メモ化関数
    table = {}
    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func

@memoize
def memFib(n):
    if ( n<=1 ):
        return 1
    else:
        return memFib(n-2) + memFib(n-1)

メモ化を用いることによって一度計算した値を記憶し，次にその値が欲しいときは，計算抜きにメモから呼び出せるようになります．
何回も同じ計算を実行するときなどに非常に早く計算できます．

実行時間の比較

お待ちかね，速度比較です．
フィボナッチ数列の第n項をFib(n)として，Fib(1)からFib(30)までを計算する時間の和を測りました．
いちいち書くのが煩雑だったので，計測過程を関数化しています．

import time
#計測用関数
def tc(func, n):
    s = time.time()
    a = [func(i) for i in range(n)]
    e = time.time() - s
    return  '{0:8.6f}'.format(e)+'秒'

#比較
print("単純＿＿：", tc(simFib, 30))
print("末尾再帰：", tc(endFib, 30))
print("繰り返し：", tc(repFib, 30))
print("行列＿＿：", tc(matFib, 30))
print("メモ化＿：", tc(memFib, 30))

結果です．

単純＿＿： 0.754400秒
末尾再帰： 0.000116秒
繰り返し： 0.000050秒
行列＿＿： 0.002787秒
メモ化＿： 0.000014秒

単純に書いた場合が圧倒的に遅いのに対し，他の場合ではかなりの高速化が行われています．
特に今回は
Fib(1)を計算⇨，Fib(2)を計算 ⇨……Fib(30)を計算
というように30回分いちいちフィボナッチ数列を計算しているので，メモ化によって大きな恩恵を受けていることがわかります．

PSM

python する man