Комментарии 13
Очень сложные рассуждения для объяснения простейшей вещи, которую школьник понимает за один урок.
Входит ли значение в список?
Если список пустой, то не входит. Иначе, если первый элемент списка равен нашему значению, то входит. Иначе вопрос сводится к проверке, входит ли он в остаток списка без первого элемента.
Вот и вся рекурсия. И никаких присваиваний.
А что, за рекурсивную обработку списков уже не гонят из профессии ссаными тряпками?
ЗЫ: Я знаю про языки с хвостовой рекурсией, но даже в них рекомендуют использовать map, filter, fold, zip и т.п., а не вот это всё.
А как, по-вашему, внутри устроены функции высокого порядка?
(defun map (f xs)
(if (null? xs)
'()
(cons (f (car xs)) (map f (cdr xs)))))На минуточку, в посте Go, а не Lisp. В Go вроде как вообще нет оптимизации хвостовой рекурсии.
А потом у людей, попытавшихся самостоятельно так написать, оказывается, что получилась не хвостовая рекурсия (классический пример – "наивная" реализация факториала вида f(0) = 1, f(x|x>0) = x*f(x-1)).
Так что нафиг, map (или, что интереснее, fold) написан один раз и многократно проверен, писать его заново, рискуя всадить ошибку, которую умные люди уже исправили 40 (или 60?) лет назад, не следует.
ЗЫ: А!!! Я не могу это развидеть: обход отсутствия Tail Call Optimization в Go:
https://go.dev/play/p/rAIgzGqAOM
keywords: trampoline function (вы наверняка такие вещи знаете, раз для вас Lisp привычный язык, оставляю на случай, если кто-то наткнётся и будет думать, что это, как и зачем).
Я без понятия, зачем автор, взявшись объяснять рекурсию, использует язык Go (и сыплет присваиваниями). Он вообще странно мыслящий человек, как я написал выше.
Тем не менее, наивная реализация факториала является примером хвостовой рекурсии, как её не записывай, и в таком качестве вполне приемлема для оптимизирующих эти вызовы трансляторов, от Лиспа до Фортрана.
Я лично в школе изучал рекурсию раньше цикла, и вполне доволен.
А трамплин - это, конечно жесть.
Наивная реализация факториала не является примером хвостовой рекурсии.
Ключевой момент: возвращаемое значение – не f(...), а n*f(...). Т.е. нам нужно сохранить текущее значение n, чтобы потом умножить на него результат функции, а значит, сохраняется и стекфрейм, заменить call на jump невозможно.
Для реализации факториала через хвостовую рекурсию нужна вторая функция, принимающая не только текущее значение n, но и аккумулятор. Например, так:
f(n) = f2(1,n)
f2(a,0) = a
f2(a,n|n>0) = f2(n*a, n-1)
Ещё лучшим примером неправильного использования рекурсии является наивное рекурсивное вычисление чисел фибоначчи. Нужно реально подумать, чтобы написать рекурсивную реализацию через хвостовую рекурсию (если не лень – попробуйте сделать и засеките, сколько времени это займёт). При этом если решите использовать fold – примерно сразу выйдете на правильное решение (ну просто потому, что через fold неправильное сделать трудно).
Тут надо тщательно определиться с терминами.
Наивная реализация факториала не является хвостовой рекурсией, если последнюю понимать узко, как буквальное расположение call перед ret и, соответственно, буквальную замену call на jmp.
Наивная реализация факториала является хвостовой рекурсией в широком, функциональном смысле, понимаемой как однократный рекурсивный вызов из функции самой себя, после которого нет никакой другой логики.
С точки зрения оптимизирующего транслятора нет никакой разницы между наивной и аккумулирующей рекурсивной реализацией факториала, в обоих случаях он осуществляет оптимизацию хвостовой рекурсии путём фактического удаления рекурсивного вызова. Вопрос разобран, например, здесь.
А так вообще целые числа переполнятся факториалом и числами фибоначчи гораздо раньше, чем стек, даже если не оптимизировать хвостовую рекурсию.
Наивная реализация факториала – не хвостовая рекурсия ни в каком смысле. Потому что умножение на n надо выполнить после рекурсивного вызова. Всё, точка. Без аккумулятора тут хвостовая рекурсия не получается.
Если компилятору хватает ума разобраться и сделать из этого говнокода хвостовую рекурсию – честь ему и хвала. Но термины подменять не надо, а то так мы дойдём того, что тут рекурсии нет вообще.
Хвостовая рекурсия - это конструкция, логически эквивалентная циклу. До раскрытия вызова умножать или после - не играет никакого значения с точки зрения схемы программы. У вас просто граница тела цикла пройдёт в другом месте. Смотрите на умножение, как на начало следующей итерации.
Техника оптимизации хвостовой рекурсии логически заключается в том, что мы как бы разворачиваем вызовы функции в подстановку её тела, а затем режем получившуюся последовательность команд на циклически повторяющиеся части. При этом не играет никакой роли, было что-то линейное после рекурсивного вызова или не было.
Зачем вы называете наиболее ясный код "говнокодом" - не очень понятно.
Вот-вот. Логически эквивалентная. Раз умножать надо _после_ получения результата – значит, не эквивалентна.
Да какая разница, до или после? Вы границу между итерациями цикла можете провести там, где хотите, перекинув лишние команды из конца в начало.
Хорошо, попробую объяснить то же самое по-другому. Рассмотрим функцию f*, представляющую собой результат частичного применения функции * (умножение) к функции f и свободному параметру. Тогда наивная запись факториала представляет собой концевую рекурсию в вашем понимании относительно функции f*. Но это просто переобозначение того, что там и так написано.
Поскольку умножение коммутативно, то конкретно факториал можно посчитать и без частичного применения - полной передачей параметров, как в вашем усложнённом примере. Но в общем случае так не прокатит.
Забавно, использование частичного применения функции в качестве аргумента практически сводит код к тому, который используется в примере с трамплином (по сути, мы свели рекурсию к концевой рекурсии, а трамплин – это просто явное разворачивание концевой рекурсии для языков, которые этого не умеют).
Кстати, есть интересный пример ручной оптимизации при использовании рекурсии – qsort. Наивная реализация делает два рекурсивных вызова, до и после разделяющего элемента, что в худшем случае (уже отсортированный массив) даёт рекурсию (не свёрнутую tail call optimization) с глубиной N. Классическая оптимизация – делать рекурсивный вызов только для меньшего по длине подмассива, а больший сортировать прямо на месте (в цикле, но с тем же успехом можно было бы и tail call).
Разбираемся с рекурсией на примере связных списков