Привет.
Вот дано определение чисел Фибоначчи:
F(0)=0, F(1)=1, F(N)=F(N-1)+F(N-2).
Мне нужно написать функцию вычисления через рекурсию и цикл.
Вот я написала:
def f1(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
def f2(n):
x, y = 0, 1
if n == 0:
return 0
for i in range(n-1):
x, y = y, x + y
return y
Объясните пожалуйста,почему f1 с рекурсией работает в 10 млн. раз медленее чем f2. В гугле есть какая то фигня про рекурсию в питоне, но на английском языке и я не понимаю.
