studies

いろいろ勉強用備忘録的な感じ

python3はじめました:とりあえずフィボナッチ数列を書いてみる

ふと読み返してみると、いつからこのブログは旅行記になったのだろう、という感じである。
最近マンネリ気味だったので仕方がない。

さて、なんとなく仕事も閑散期を抜けそうな気がするので、私も心新たに新しい言語を試してみている。
python3である。

とりあえず、python tutorialというサイトが充実しているので、これを見ながら勉強している。

4.6関数定義で出てくるフィボナッチ数列の定義が、ちょっとテクニックを使っていて「おっ」と思った。
そこで、自分でも複数パターン、フィボナッチ数列を返す関数を書いてみたので晒してみることにする。

本家のfib関数は、

# write Fibonacci series up to n

ということで、標準出力含めた形のプロシージャとなっているが、ここでは、
引数nに対して、フィボナッチ数列の第n項を返す関数として定義する。
つまり、副作用のない関数にしておく。
こうしたほうが違いがはっきりするだろう。

この形で本家のfib関数と同じロジックで書くと、次のようになる。

def fib_ver1(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b
    return a

いっぽう、ふつう教科書とかにありそうなのは、次のような再帰的な記述だ。

def fib_ver0(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fib_ver0(n-1) + fib_ver0(n-2)

これは数学的にも、すっきりしていて美しい。
のだが、何回も同じ関数を呼び出すことになり、スタックが有限であるコンピュータの処理的には良くない。

メモ化を使うと次のようになるだろう。

memo = [0, 1]
def fib_ver2(n):
    global memo
    if len(memo) > n:
        return memo[n]
    else:
        ans = fib_ver2(n-1) + fib_ver2(n-2)
        memo.append(ans)
        return ans

グローバルで定義されたリストに、計算結果をメモしておくわけである。
メモリを効率的に使い、ver0で何回も同じことをしていたのを回避している。

for文が死んでもいやであるという純粋主義者がver1を再帰的に書くには、
第n項を返すというインタフェースは諦めて、第n項と第n+1項からなるリストを返すということになるだろう。

def fib_ver1_rec(n):
    if n == 0 :
        return [0, 1]
    else:
        a, b = fib_ver1_rec(n-1)
        return [b, a+b]

これを見ると、ver0では再帰呼び出しを2つ行っているのに対して、ver1では再帰呼び出しを1つに済ませているのがよくわかる。
python tutorialの4.6ではさらっと書かれているが、そういう工夫がされていることには、注意を払うべきポイントだと思う。