рекурсия -- можно быстрее?

nsk.coder

unread,

Oct 7, 2010, 12:59:42 AM10/7/10

to SPb Haskell User Group

Добрый день!
Полагаю, что каждый, кто пишет в рекурсивном стиле, задумывается об
эффективности.

Недавно, на таком простом примере вычисления чисел Фиббоначи
споткнулся о страшные тормоза:

fib 1 = 1
fib 2 = 1
fib n = fib (n-1) + fib (n-2)

Уже при n=35 это длительные задержки, при n=40 -- двухядерный ноутбук
прилично висит уже минуты.

Можно ли процесс ускорить? Наверняка это достаточно популярная тема,
особенно избитый пример с числами Фиббоначи. Ведь аналогичная задача в
императивном программировании, оформленная в виде цикла считается
мгновенно для указанных n!!

Eugene Kirpichov

unread,

Oct 7, 2010, 1:06:21 AM10/7/10

to spb...@googlegroups.com

7 октября 2010 г. 8:59 пользователь nsk.coder <nsk....@gmail.com> написал:

Ну ясен хрен: сортировка миллиона чисел пузырьком на си делается
несколько минут, а radix sort на ruby справляется за долю секунды -
сенсация, динамически типизированные интерпретируемые языки победили
статически типизированное низкоуровневое старье!!111

Тут дело не в функциональности языка и не в циклах против рекурсии, а
в том что используются абсолютно разные алгоритмы вычисления. Как на
императивном языке можно реализовать неэффективный алгоритм, так и на
функциональном - эффективный.

Вот эта версия будет быстро вычислять хоть миллиардное число Фибоначчи.

fib :: Int -> Int
fib = fst . fib2

fib2 :: Int -> (Int, Int)
fib2 0 = (1, 1)
fib2 1 = (1, 2)
fib2 n
| even n = c `seq` (a*a + b*b, c*c - a*a)
| otherwise = c `seq` (c*c - a*a, b*b + c*c)
where (a,b) = fib2 (n `div` 2 - 1)
c = a + b

>
> --
> Отправить сообщение в SPb HUG: spb...@googlegroups.com
> Отменить подписку: spbhug-un...@googlegroups.com
> Страница группы: http://groups.google.com/group/spbhug?hl=ru

--
Eugene Kirpichov
Senior Software Engineer,
Grid Dynamics http://www.griddynamics.com/

nsk.coder

unread,

Oct 7, 2010, 4:36:37 AM10/7/10

to SPb Haskell User Group

Спасибо!!

Великий Гугл (правда на нелюбимом английском) дал еще несколько
подходящих решений, мож кому тоже будет интересно:

http://www.cubbi.org/serious/fibonacci/haskell.html
http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
http://en.literateprograms.org/Fibonacci_numbers_(Haskell)

Тогда, видимо, задать вопрос следовало иначе:

есть ли общие приемы писать рекурсивные функции быстрыми и где об этом
можно узнать?
(например, я хотел бы узнать что-то про "хвостовую рекурсию" и можно
ли ее применять в этом случае)

Ответ типа "руки кривые" как-то грустно звучит :(

On 7 окт, 12:06, Eugene Kirpichov <ekirpic...@gmail.com> wrote:
> 7 октября 2010 г. 8:59 пользователь nsk.coder <nsk.co...@gmail.com> написал:

Eugene Kirpichov

unread,

Oct 7, 2010, 4:40:09 AM10/7/10

to spb...@googlegroups.com

7 октября 2010 г. 12:36 пользователь nsk.coder <nsk....@gmail.com> написал:

> Спасибо!!
>
> Великий Гугл (правда на нелюбимом английском) дал еще несколько
> подходящих решений, мож кому тоже будет интересно:
>
> http://www.cubbi.org/serious/fibonacci/haskell.html
> http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
> http://en.literateprograms.org/Fibonacci_numbers_(Haskell)
>
> Тогда, видимо, задать вопрос следовало иначе:
>
> есть ли общие приемы писать рекурсивные функции быстрыми и где об этом
> можно узнать?

Видимо, имеется в виду "Есть ли общие приемы преобразования
рекурсивных программ в итеративные, избавления от экспоненциальной
рекурсии итп"?
Есть.

См. напр. http://fprog.ru/2009/issue3/ , статья "Элементы
функциональных языков", глава "Хвостовой вызов".

> (например, я хотел бы узнать что-то про "хвостовую рекурсию" и можно
> ли ее применять в этом случае)

Проблема у примера с фибоначчи не в том, что рекурсия не хвостовая, а
в том, что она древовидная и экспоненциальная - куча всего лишний раз
пересчитывается. Это не имеет вообще никакого отношения к явлению
рекурсии как таковой, просто использован неудачный алгоритм.