Python実行例 フィボナッチ数

# フィボナッチ数
# F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1} で定義される

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

# 自分自身を２回再帰呼び出ししているので、n が大きくなると
# かかる時間が指数関数的に増大する。
# fibo1(35)
# で答えが出るまでに 5 秒くらい。
# それより大きい数では飛躍的にかかる時間が長くなる。

# フィボナッチ数(if 文と for 文を使って)

def fibo2(n):
    if (n == 0):
        return 0
    elif (n == 1):
        return 1
    else:
        k0 = 0
        k1 = 1
        for i in range(2, n+1):
            k2 = k1 + k0
            k0 = k1
            k1 = k2
        return k2

# fibo2(100000)
# くらいでも一瞬で答えが出る

# フィボナッチ数(浜田の解法1)

# n が奇数の時、F_n = F_{(n+1)/2}^2 + F_{(n-1)/2}^2
# n が偶数の時、F_n = F_{n/2 + 1}^2 - F_{n/2 - 1}^2
# という性質を使う

def fibo3(n):
    if (n == 0):
        return 0
    elif (n == 1):
        return 1
    elif (n%2 == 1):
        return fibo2(n//2+1)**2 + fibo2(n//2)**2
    else:
        return fibo2(n//2+1)**2 - fibo2(n//2-1)**2

# フィボナッチ数(浜田の解法2)

# fibo3 では実は fibo2 を2回呼び出しているので余分に繰り返し
# 計算していることになるので、さらに改善できるはずである
# (効果が目に見えるのはよほど大きい n の場合になるが)。
# この関係式を繰り返し適用することにより、計算量オーダーをさらに
# 改善できることがわかる。
# 下に、fibo_i(n) という、隣り合うフィボナッチ数のペアを返す内部関数を
# 定義し、その内部関数を呼び出す形で fibo4(n) を定義する。

def fibo_i(n):
    if (n == 0):
        return [1, 0]
    elif (n == 1):
        return [0, 1]
    elif (n == 2):
        return [1, 1]
    else:
        l = fibo_i(n//2)
        a = l[0]
        b = l[1]
        c = l[0]+l[1]
        if (n%2 == 1):
            return [c**2 - a**2, c**2 + b**2]
        else:
            return [b**2 + a**2, c**2 - a**2]

def fibo4(n):
    if (n == 0):
        return 0
    elif (n == 1):
        return 1
    elif (n == 2):
        return 1
    else:
        l = fibo_i(n//2)
        a = l[0]
        b = l[1]
        c = l[0]+l[1]
        if (n%2 == 1):
            return c**2 + b**2
        else:
            return c**2 - a**2

この他にも色々試して、追加してください。