Python(11)再帰のお勉強:フィボナッチの数列

前の関連記事：Python(10)再帰のお勉強:自然数の階乗

こんどはフィボナッチの数列の例です。漸化式で表現できるので再帰で表現できるのですが、自分自身を2回呼び出すので非線形再帰になります。

フィボナッチの数列の例

$$\begin{cases}
{F}_{0}=1  \\
{F}_{1}=1  \\
{F}_{n}={F}_{n-1}+{F}_{n-2}&(n > 1)  
\end{cases}$$
この漸化式で表せる数列です。

1, 1, 2, 3, 5, 8, 13, 21, 34 …

この第n項(nは負でない整数)を求める関数fib(）をPythonで作ります。

def fib(n):
    if n > 1:
        return fib(n-1) + fib(n-2)
    else:
        return 1
print(fib(4))

これで第4項の5出力されます。

3行目で自分自身を2回呼び出していますので非線形再帰になります。

ちょっと想像しただけではどうやって動作しているのかわからないので図にしてみます。

図にしやすくするために引数で計算している式を外にだします。

def fib(n):
    if n > 1:
        n -= 1
        p = fib(n)
        n -= 1
        q = fib(n)
        m = p + q
        return m
    else:
        return 1
print(fib(4))

これで実行している行を図に描いてみます。

再帰の折り返しで色を変えています。
再帰の式はシンプルなのに図にして実行内容をみてみるととても複雑ですね。

fib(n)のときfib(n)は何回呼び出されるのか？

fib(n)が呼ばれる回数はn=0とn=1のときは1回ですが、n>1となると何回になるのでしょう？

n=2のとき3回、n=3のとき5回、n=4のとき9回、n=5のとき15回、、、

1回呼ぶと自分自身で2回呼ぶから、といってなにか公式があるのかと思いましたが見つかりませんね。

折り返す条件によって呼び出し回数が変わるので公式にはできないのかも。

ちょっと何回になるのか考えてみます。

# -*- coding: utf-8 -*-
def fib(n):
    c[0] += 1
    if n > 1:
        return fib(n-1) + fib(n-2)
    else:
        return 1
c = [0]
print(fib(4))
print("fib(n)の呼び出し回数:{}".format(c[0]))

安易にリストの要素をグローバル変数に使って数えます。

def fib(n):
    c[0] += 1
    if n > 1:
        return fib(n-1) + fib(n-2)
    else:
        return 1
for i in range(10):
    c = [0]
    fib(i)
    print(c[0])

第0項から第9項まで数えてみました。

1, 1, 3, 5, 9, 15, 25, 41, 67, 109 …

規則性見出せず、、、

そういうときは差をとってみるとかしたはず、、、

0, 2, 2, 4, 6, 10, 16, 26, 42 …

おお、差の数列を作ってみると第2項以降は前2項の和になっていてフィボナッチ数列と同じパターンになっていますね。

とりあえずこの差の数列について漸化式を作ります。
$$\begin{cases}
{t}_{0}=0  \\
{t}_{1}=2  \\
{t}_{n}={t}_{n-1}+{t}_{n-2}&(n > 1)
\end{cases}$$

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

このt(n)を使ってfib(n)を計算するときにfib(n)が呼び出される回数を計算するT(n)を定義します。
うーん、もうちょっと数学の知識があればもっと美しくできそうですけど、いまは答えを知りたいだけなのでこのまま計算しちゃいます。

def t(n):
    if n == 0:
        return 0
    elif n == 1:
        return 2
    else:
        return t(n-1) + t(n-2)
def T(n):
    if n > 0:
        return T(n-1) + t(n-1)
    else:
        return 1
print(T(9))

これでfib(9)のときのfib(n)の呼び出し回数が109回と求まります。

再帰を使うと計算回数が増えて大変、という主旨でこの節を書き始めたのですけど、再帰関数は使い方がわかってしまうと便利ですね。

再帰を使えばこんな風にとりあえず漸化式を作ってしまえば答えを求めるプログラムが書けてしまいます。

答えが求まるかどうかはあとはコンピュータののがんばりにかかってきます。

T(30)ぐらいまでは待てますけどT(40)になると答えが返ってくるまですごく時間がかかります。(私のマシン環境はウェブブラウザ(1)最速はChrome？と同じです。）

T(30) = 2692537

T(40) = 331160281

fib(40)を求めるのにfib(n)は331,160,281回も呼び出されているということです。3億回！

ちなみにfib(40)=165580141でした。

次の関連記事:Python(12)二重再帰の再帰を除去する