Почему мне кажется что хвостовая рекурсия это ненадежный хак? — такой частный случай рекурсии при котором не происходит ошибка переполнения стека.
Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
A>Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
ну это должно легко решаться диагностикой. Типа метишь вызов тэгом TAIL, если по твоей задумке это хвостовая рекурсия, чтобы компилятор мог отрапортовать нарушение.
Здравствуйте, dilmah, Вы писали:
A>>Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
D>ну это должно легко решаться диагностикой. Типа метишь вызов тэгом TAIL, если по твоей задумке это хвостовая рекурсия, чтобы компилятор мог отрапортовать нарушение.
т.е. язык должен поддерживать как минимум две формы вызова функции — нормальную, и для хвостовой рекурсии,
а если ты забыл написать "TAIL" тебе никто не напомнит, т.к. сама по себе рекурсия нормальный механизм, если она неглубокая.
A>т.е. язык должен поддерживать как минимум две формы вызова функции — нормальную, и для хвостовой рекурсии, A>а если ты забыл написать "TAIL" тебе никто не напомнит, т.к. сама по себе рекурсия нормальный механизм, если она неглубокая.
ну не 2 формы, а 1 форма по разному квалифицированная.
В данном случае полный аналог ключевого слова override, добавленного в новый С++.
Здравствуйте, dilmah, Вы писали:
A>>т.е. язык должен поддерживать как минимум две формы вызова функции — нормальную, и для хвостовой рекурсии, A>>а если ты забыл написать "TAIL" тебе никто не напомнит, т.к. сама по себе рекурсия нормальный механизм, если она неглубокая.
D>ну не 2 формы, а 1 форма по разному квалифицированная. D>В данном случае полный аналог ключевого слова override, добавленного в новый С++.
D>>ну не 2 формы, а 1 форма по разному квалифицированная. D>>В данном случае полный аналог ключевого слова override, добавленного в новый С++.
A>это есть в каком-то языке?
нет, я имею в виду что механизм аналогичен тому, что в майкрософтовском С++ можно пометить метод квалификатором override:
class X : public B {
virtual void foo() override;
};
после этого компилятор будет ругаться если вдруг в базовом классе нет метода foo с такой же сигнатурой.
Это решает такую же проблему как у тебя с хвостовой рекурсией -- легко что-то поменять или ошибиться и получить проблему.
Здравствуйте, dilmah, Вы писали:
D>>>ну не 2 формы, а 1 форма по разному квалифицированная. D>>>В данном случае полный аналог ключевого слова override, добавленного в новый С++.
A>>это есть в каком-то языке?
D>нет, я имею в виду что механизм аналогичен тому, что в майкрософтовском С++ можно пометить метод квалификатором override:
это я понял, я к тому что в каком нибудь языке где есть хвостовая рекурсия, такой квалификатор есть?
в хаскеле\немерле\окамле\другом ФЯ
Здравствуйте, Abyx, Вы писали:
A>Почему мне кажется что хвостовая рекурсия это ненадежный хак? — такой частный случай рекурсии при котором не происходит ошибка переполнения стека. A>Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
В Scala есть модификатор @tail, который обозначает, что функция обязана быть хвостовой. Если не так, то компилятор выводит ошибку.
Здравствуйте, Abyx, Вы писали:
A>Почему мне кажется что хвостовая рекурсия это ненадежный хак? — такой частный случай рекурсии при котором не происходит ошибка переполнения стека. A>Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
Думаю, в том числе поэтому рекомендуют пользоваться стандартными конструкциями map, folr и др., реализованными в стандартной библиотеке, а не вводить рекурсию "вручную".
Здравствуйте, Abyx, Вы писали:
A>Почему мне кажется что хвостовая рекурсия это ненадежный хак? — такой частный случай рекурсии при котором не происходит ошибка переполнения стека.
Видимо, вы пока еще мало писали хвостаторекурсивных ф-ий.
A>Что ее легко заменить на не-хвостовую рекурсию, не заметить этого и потом ловить переполнения стека на каждом 100м запуске программы?
Заменить рекурсию на не хвостовую и не заметить -- это очень сложно, т.к. признак хвостатости очень прост -- если после рекурсивного вызова ничего не делается (результат рекурсивного вызова и является результатом ф-ии), то ф-ия хвостатая.
В языках с ленивым порядком вычислений добавляются свои интересности -- даже не хвостатая ф-ия может вычилсяться инкрементально, не сжирая стек (и наоборот, хвостатая может отжирать стек накапливая невычисленные цепочки), но это уже отдельная песня (хотя тоже ничего особенного и дело привычки).
