Кабінет психопатологічної евтаназіології (
euthanasepam) wrote2021-07-12 10:52 am
![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png)
Entry tags:
Пролетарська рекурсія за ваш рахунок
На популярному сайті Rosetta Code з прикладами програм на розмаїтих програмувальних мовах є зразки вирішення всіляких типових математичних, алгоритмічних і хтозна ще яких проблем.
Погляньмо, наприклад, на рекурсивний пошук якогось числа у послідовності Фібоначчі, запрограмований мовою Паскаль:
http://rosettacode.org/wiki/Fibonacci_sequence#Pascal
function fib(n: integer): integer; begin if (n = 0) or (n = 1) then fib := n else fib := fib(n-1) + fib(n-2) end;
Гарно? Авжеж. Вельми гарно. Тішить серце і милує око.
Але коли ви цей алгоритм відкомпілюєте і запустите на виконання для числа, скажімо, 64, то встигнете
Для порівняння: ітеративний алгоритм працює блискавично навіть для досить великих чисел, що вмістяться у комп’ютерну пам’ять.
Отож, мораль: коли вам якесь
P. S.
Нарешті порахувало для 64:
10610209857723 real 5257m47,799s user 0m0,000s sys 0m0,015s
no subject
Ну ти й терплячий
no subject
Результат красномовний.
Як хтось розумний казав — чи то Кнут, чи то Вірт, — що простий і «тупий» алгоритм зазвичай кращий за кручений та вишуканий.
no subject
Але не цього разу :). Бо найпростіший алгоритм якраз рекурсивний.