Русскоязычное программирование

Информация о пользователе

Привет, Гость! Войдите или зарегистрируйтесь.



Хвостовая рекурсия

Сообщений 1 страница 2 из 2

1

"тот факт, что хвостовая рекурсия преобразуется в эквивалент цикла 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)

0

2

Цикл заменяется на хвосто-рекурсивную процедуру

Вообще-то все строго наоборот - в функциональном программировании при компиляции и просто в целях оптимизации рекурсии разворачивают в цикл (поскольку в труъ их нет). Причины такого поступка очевидны стали еще в 70-х - большая нагрузка по памяти (тогда память была критичным условием для программ). А все потому что нужно было скрестить ежа с ужом - и производительность нужна и возможность запихнуть цикл в параметр.
И еще: Ваши примеры сферических коней в вакууме убийственны. Все уже поняли сколько существует способов записать a + b (или a - b - суть один процесс) - до самого садового овоща. Людей интересует возможность реального применения предлагаемых фич. Богатство выражения синтаксического сахара это здорово, но может привести к синтаксическому диабету :). Давайте примеры, хотя бы которые не выражаются императивно однострочным выражением вида a операция б или z = x + y. Ну не по фень-шую это. Я понмаю в программировании в некотором роде застой - новых фич приходит мало, но давайте уже не будем рассматривать то, что имеет сомнительную практическую ценность.

Отредактировано utkin (2018-01-30 09:46:08)

0