友人から、Python で効率的なフィボナッチ関数を作成するという課題が与えられました。そこで、再帰を実行するさまざまな方法についてテストを開始しました (複雑なアルゴリズムを考えるための高度な数学スキルはありません。効率的なフィボナッチ関数を見せないでください。それは問題ではありません)。
次に、2 つの異なる解決策を試しました。
解決策 1:
def fibo(n):
if n > 1:
return fibo(n-1)+fibo(n-2)
return 1
解決策 2:
def fibo(n):
if n < 1:
return 1
return fibo(n-1)+fibo(n-2)
次に、それぞれに対してこれを実行しました。
res = map(fibo, range(35))
print res
ここで、効率に違いがあるのではないかと思いました (正確な理由はわかりません)。しかし、私は小さな違いを期待していました。結果は私を完全に吹き飛ばしました。その差は大きかった。1 つ目は 7.5 秒かかりましたが、2 つ目は驚異的な 12.7 秒かかりました (ほぼ 2 倍です!)。
誰かが私に理由を説明できますか? それらは本質的に同じではありませんか?