| Меню сайта |
|
 |
| Статистика |
Онлайн всего: 1 Гостей: 1 Пользователей: 0 |
|
|
 | |  |
| Главная » 2015 » Декабрь » 11 » Журнал Пушыстого : Односвязные списки рекурсия
18:42 Журнал Пушыстого : Односвязные списки рекурсия |
В учебниках по языкам про односвязные списки (LISP и тд) часто начинают с примера навроде суммирования списка ( перед следующей главой с foldl/foldr).
Сначала показывается пример, как думает человек на естественной рекурсии: что бы просуммировать список, надо посчитать сумму без первого элемента, а затем добавить к ней этот первый элемент.
SumList(L) = Empty(L) ? 0 : (Head(L) + SumList(Tail(L)))
Затем грозят пальчиком, и объясняют что так низзя. Нужно применять "хвостовую рекурсию":
SumList(L, SUM) = Empty(L) ? SUM : SumList(Tail(L), Head(L) + SUM)
Что бы программа не кушала стек, и работала быстрей. Иначе программа не сожрёт большой инпут, будет глючить и тормозить. Вкратце: если последняя инструкция в процедуре - это вызов процедуры, то место под локальные переменные можно грохнуть до вызова, всё равно больше не понадобятся. И точку возврата оставить старую, а не создавать новую в конец текущей процедуры (всё равно после неё - сразу jump в старую точку).
Спрашивается, зачем язык, в котором всё равно надо думать в императивных терминах while и присваиваний, которые объявлены "фуу" и "бяка"?
Вот так вот думать:
SUM = 0
while (not Empty(L)) {
SUM += Head(L)
L = Tail(L)
}
return SUM
Получается, что такой язык - это просто ещё один такой странный ассемблер. Чудности которого надо уважать, иначе будет протечка абстрации, тормоза, нехватка памяти.
И спрашивается, как явно попросить транслятор проверить, не забыл ли я случайно использовать хвостовую рекурсию? А то ведь можно с недосыпа думать что всё тип-топ, ан-нет, хвостовая рекурсия оказалась не хвостовой, и собирается покусать всех остальных, а не только себя.
|
|
Просмотров: 289 |
Добавил: supoinclus
| Рейтинг: 0.0/0 |
| |
 | |  |
|
| Вход на сайт |
|
|
| Поиск |
|
|
| Календарь |
|
|
| Архив записей |
|
|
|
