Речь пойдет не о Леонардо Фибоначчи, золотом сечении и поиске смысла и закономерностей там где их нет. Речь о числах Фибоначчи и их вычислении.
Благодаря числам Фибоначии можно наглядно продемонстрировать преимущество итераций перед рекурсией.
f0 = 0 f1 = 1 fn = fn-1 + fn-2
n-число последовательности равно сумме двух предыдущих чисел последовательности.
Все просто и красиво.
$q = 0;
sub f {
local ($n) = (@_);
$q++;
if ($n < 2)
{
return $n;
}
else
{
return f($n - 2) + f($n - 1);
}
}
print "n=", $ARGV[0], " f(", $ARGV[0], ")=", f($ARGV[0]), " Calls: $q \n";
n=7 f(7)=13 Calls: 41
n=25 f(25)=75025 Calls: 242785
n=30 f(30)=832040 Calls: 2692537
Для 50-го числа я даже запускать не стал.
Второй вопрос: чему равно f(0).
Русская wikipedia: Последовательность начинается с 1. (Хотя там же приводится ссылка, где последовательность начинается с 0)
Английская wikipedia: Последовательность начинается с 0.
Идем на The Weekly Source Code 13 — Fibonacci Edition и наблюдаем следующее в первом же примере:
F# let rec fib n = if n < 2 then 1 else fib (n-2) + fib(n-1) для 0 вернет 1, мелочь, а приятно.
Хотя по большему счета какая разница. Но зато сколько возможных реализаций.
