"тот факт, что хвостовая рекурсия преобразуется в эквивалент цикла while, является критическим для возможности использования рекурсивных формулировок алгоритмов."
(Лис: и если я правильно понимаю, именно в такие штури превращвются циклы в лямбда-исчислении)
"в текущем стэк фрэйме заменяются actual parameters на новые
и вычисления продолжаются без создания нового фрэйма.
По сути вместо рекурсивной функции получился цикл."
"tail call — если функция последним действием вызывает функцию, возвращая её результат, то можно заменить это последнее действие на некий аналог goto в начало другой функции. Собственно, вместо call-вычисления-return-return получается goto-вычисления-return и можно забыть обо всём, что было в оригинальной функции."
"tail recursion — частный случай, когда функция последним действием вызывает себя."
"Цикл заменяется на хвосто-рекурсивную процедуру, принимающую в качестве аргументов переменные состояния, используемые циклом.
Например, вот императивная процедура и ее хвосто-рекурсивный аналог:
int sum(int a,int b) {
for(int s = 0, i = a; i < b ; ++i)
s += i;
return s;
}
sum a b = sum' 0 a
where sum' s i = if i>=b
then s
else sum' (s+i) (i+1)
"
Отредактировано Лис (2018-01-30 00:46:43)
. Давайте примеры, хотя бы которые не выражаются императивно однострочным выражением вида a операция б или z = x + y. Ну не по фень-шую это. Я понмаю в программировании в некотором роде застой - новых фич приходит мало, но давайте уже не будем рассматривать то, что имеет сомнительную практическую ценность.