再帰
pypyはpythonよりも再帰が遅い。なぜかはわからないけど、そういうものと覚える。DFSなどでよく使われる。
よくあるのは「1からnの整数の和を返すプログラム」で、
def sum(n):
if n < 1:
return n
return n + sum(n-1)
s = sum(100)
print("1から100の合計は", s, "です")
こんな感じになる。再帰を使わなければ
def sum(n):
ret = 0
for i in range(1, n + 1):
ret += i
return ret
s = sum(100)
print("1から100の合計は", s, "です")
こう。
atcoderの出しているV - 2.05.再帰関数がむちゃくちゃわかりやすい。
フィボナッチ数列
よく見るこれ。定義は
フィボナッチ数列は、「2つ前の項と1つ前の項を足し合わせていくことでできる数列」のことです。数列は「1,1」から始まり、1, 1, 2, 3, 5, 8, 13, 21…と続いていきます。
図形にすると美しくなり、黄金比というやつになる
再帰関数と再帰を使わない解法に計算時間がまとまっていてわかりやすい。
def fib_recursive(n):
if n <= 1:
return n
else:
return fib_recursive(n - 1) + fib_recursive(n - 2)
def fib_while(n):
list_ = []
i = 0
while i < n:
if len(list_) < 2:
list_.append(i)
if len(list_) >= 2:
list_.append(list_[0] + list_[1])
list_.pop(0)
i += 1
return list_[1]
`
使わないほうがわかりやすい気さえするなあ。