Что такое хвостовая рекурсия? Душкин объяснит
Вставка
- Опубліковано 16 лют 2022
- Для организации итеративных процессов в функциональных языках программирования используется рекурсия. Один из её типов - хвостовая. Узнаем, как она выглядит.
Курс по функциональному программированию на Udemy: www.udemy.com/course/fp-haskell/
ТГ-канал Романа Душкина: t.me/drv_official
#ФП #Программирование #Функция #ФункциональноеПрограммирование #Haskell #Хаскель #Хаскелл #Видеошпаргалка #РоманДушкин #ДушкинОбъяснит #Список #Функция #ОбработкаСписков #Структура #СтруктураДанных
божечки, я в результате копаний с рекурсией пришел к теме эволюции и бифуркационных диаграмм :)
Это же очень круто! Поздравляю :) Обратите внимание на мои видео по биотехнологиям. Ну и генетические алгоритмы я тоже уже рассмотрел.
Все видео по функциональному программированию в одном плейлисте: ua-cam.com/video/bPCBb1U56yw/v-deo.html
И вы всегда можете обратиться к нам за консультациями.
А ещё вы можете написать мне в ТГ: @rdushkin
Спасибо! Интересно. А в clojure списки тоже с рекурсией?
Должны быть. Но я не знаю.
какой красивый почерк! божечкии
Был бы ещё красивее, если бы я не спешил.
length это не хвостовая рекурсия, т.к. последняя операция не вызов функции length, а сложение
То же самое и про map: последняя операция это (:), а не вызов map.
Ну они всё равно похожи на хвостовую и могут вычисляться в постоянном объёме памяти же.
Для образца _ фраза "всё, что угодно" подходит и для образца х (переменная). Правильная фраза: "связывания с образцом (то бишь с переменной х) не происходит".
Да, точно. Там ещё значение _|_ по-разному обрабатывается, с очевидностью.
Ещё одна оптимизация это build-foldr в цепочке вычислений: там списки вообще не строятся.
Благодарю за важное дополнение.
Надо было добавить, что компилятор для оптимизации хвостовую рекурсию заменяет циклом (уже на языке C--)
Да, не всё помнишь во время записи.
Мне казалось хвостовая рекурсия должна быть что-то вроде:
```
length a = go a 0
where
go [] x = x
go (_:as) x = go as (x+1)
```
Да, всё так. Это классический вариант - аккумулятор. В следующем своём видео я про это рассказываю.
@@dushkin_will_explain да, посмотрел)
Конечно, как мне кажется, спорное решение подавать сначала нехвостовую рекурсию как хвостовую в видео про "хвостовую рекурсию", а после, в другом видео про аккумулятор, сделать оговорку на настоящесть
@@MechanicalFreaks, увы, это издержки производства.
@@dushkin_will_explain понятно, но всё равно - Вы молодец)
@@MechanicalFreaks, благодарю. Стараюсь просвещать наших людей в силу своих сил и способностей.