研究に少し行き詰まったので再帰で遊ぶ

Python 研究

未だに再帰がよく理解しきれていない若輩者なのですが・・・


研究の気分転換に少し再帰を勉強する。
Algorithms with Python / 再帰定義


で、再帰の何が分かってないかよく分かっていなかったかだけど、根本的に再帰の動作が分かっていませんでした。
そのために、普通の再帰と末尾再帰の違いがよく分かっていなかったというしょうもない罠でした。

再帰呼び出しのあとに「後に続く処理」がなければ、情報を保存する必要がなくなるわけだ。

こういう呼び出しが「末尾呼び出し」であり、再帰呼び出しすべてが末尾呼び出しであれば「末尾再帰関数」というらしい。


http://http://d.hatena.ne.jp/jyukutyo/20081111/1226368924

実にわかりやすい解説だ。


というわけで、フィボナッチ数列を求めるプログラムの時間を計測してみる。
http://hamasta.g.hatena.ne.jp/hamasta/20060909/p1

# -*- coding : utf-8 -*-

def timer(func, *args):
    import time
    start = time.clock()
    return func(*args), time.clock() - start

def fibo(n):
    if n == 0 or n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)


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

print "fibo()", timer(fibo,40)
print "fibo2()", timer(fibo2,40)

fibo()が普通の再帰で書いたフィボナッチ数列
fibo2()が末尾再帰のフィボナッチ数列

実行結果はこんな感じ。

fibo() (165580141, 88.439999999999998)
fibo2() (165580141, 0.0)

なんかもうフィボナッチ数列の40番目を求める辺りから、fibo()はえらいことになる。
ぼこぼこと二分木がうまれるので、当然っちゃ当然か。
fibo2()は実行時間0.0秒というのはすんごい早いくらいのノリで理解しました。
この辺りの正確な時間の測定はまた別の話ですからね。

ちなみに、末尾再帰の方は

RuntimeError: maximum recursion depth exceeded

が出るまで、ひたすら0.0が続く

(225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626L, 0.0)

こんな感じっす。
もはやこの数字が正しいのかどうかも分からない。


ああもう、末尾再帰が強すぎる。
少し勉強になった。