Загрузка не удалась. Возможно, проблемы с правами доступа?

Различия

Показаны различия между двумя версиями страницы.

--- haskell:fibb [15/10/2014 18:47] – vlasov
+++ haskell:fibb [15/10/2014 18:54] – vlasov
@@ Строка 55: / Строка 55: @@
 </code>
-Более интересно превращение в линейную рекурсию с аккумулятором:
+Сделаем аналог его, но уже с рекурсией вместо цикла. Рекурсия получится линейной, и добавится новый параметре __//аккумулятор//__:
 <code haskell>
-fib a b 0     = a
+f a b 0 = b
-fib a b (c+1) = fib (a+b) a c
+f a b n = f b (a+b) (n-1)
+fib n = f 1 1 n
 </code>
 запуск осуществляется так:
 <code haskell>
-fib 0 1 n
+fib n
 </code>
+Этот вариант уже не имеет проблемных мест и позволяет вычислять даже 100000-й элемент последовательности за 0.5-1.5 минуты на ноутбуке.
 Другой вариант из сайта [[http://www.haskell.org/haskellwiki/The_Fibonacci_sequence|The Fibonacci sequence]] с аккумулятором и //хвостовой рекурсией// (используя расширения языка):