Форум программистов, компьютерный форум CyberForum.ru

Чем отличается хвостовая рекурсия от обычной рекурсии? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 63, средняя оценка - 4.81
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
10.01.2013, 22:15     Чем отличается хвостовая рекурсия от обычной рекурсии? #1
Собственно вопрос сверху. Если не затруднит, то покажите пример факториала с хвостовой и с обычной рекурсией. Буду крайне благодарен.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2013, 22:15     Чем отличается хвостовая рекурсия от обычной рекурсии?
Посмотрите здесь:

C++ Рекурсия от рекурсии
C++ Чем отличается С++ от Visual С++?
Чем отличается ln , lg, и log ? C++
C++ Чем отличается this от *this?
C++ Хвостовая рекурсия
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,917
Записей в блоге: 2
Завершенные тесты: 1
10.01.2013, 22:25     Чем отличается хвостовая рекурсия от обычной рекурсии? #2
Цитата Сообщение от aleksand Посмотреть сообщение
Если не затруднит, то покажите пример факториала с хвостовой и с обычной рекурсией.
Хвостовая рекурсия
Есть пример как раз для факториала
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
10.01.2013, 22:30  [ТС]     Чем отличается хвостовая рекурсия от обычной рекурсии? #3
Цитата Сообщение от Croessmah Посмотреть сообщение
Хвостовая рекурсия
Есть пример как раз для факториала
Уже перечитал эту статью вдоль и поперёк, но понять не могу где здесь рекурсивный вызов функцией самой себя является её последней операцией?
Тут вижу что только 1 раз вызывается функция factorial, а потом рекурсивно считается fac_times.
C
1
2
3
4
5
6
7
8
int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}
 
int factorial (int n) {
    return fac_times (n, 1);
}
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,917
Записей в блоге: 2
Завершенные тесты: 1
10.01.2013, 22:55     Чем отличается хвостовая рекурсия от обычной рекурсии? #4
Цитата Сообщение от aleksand Посмотреть сообщение
но понять не могу где здесь рекурсивный вызов функцией самой себя является её последней операцией?
C++
1
return fac_times(n - 1, acc * n);
И в той же статье рядом код не хвостовой рекурсии:
C++
1
return n * factorial(n - 1);
Найдите отличия =)
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
10.01.2013, 23:53  [ТС]     Чем отличается хвостовая рекурсия от обычной рекурсии? #5
Цитата Сообщение от Croessmah Посмотреть сообщение
И в той же статье рядом код не хвостовой рекурсии:
C++
1
return n * factorial(n - 1);
Найдите отличия =)
Кажется понял, отличие в том, что в хвостовой последнее что делается в коде это делается вызов рекурсии(именно её одной без всяких там умножений, делений и тому прочего), а в нехвостовой как раз-таки делается что-то добавочное к рекурсивному вызову. Верно я всё понял?
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11845 / 6824 / 771
Регистрация: 27.09.2012
Сообщений: 16,917
Записей в блоге: 2
Завершенные тесты: 1
10.01.2013, 23:56     Чем отличается хвостовая рекурсия от обычной рекурсии? #6
Цитата Сообщение от aleksand Посмотреть сообщение
Верно я всё понял?
Собственно, в той статье в википедии написано:
Стоит отметить, что другой, более естественный рекурсивный способ вычисления факториала, приведённый ниже, не является хвостово-рекурсивным, так как в каждом вызове функции после рекурсивного вызова производятся дополнительные операции, а именно умножение на n.
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
11.01.2013, 00:01  [ТС]     Чем отличается хвостовая рекурсия от обычной рекурсии? #7
Цитата Сообщение от Croessmah Посмотреть сообщение
Собственно, в той статье в википедии написано:
Спасибо, разобрался. Что-то под вечер совсем голова не работает видимо.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
11.01.2013, 09:39     Чем отличается хвостовая рекурсия от обычной рекурсии? #8
На самом деле на википедии какая-то лажа. Суть хвостовой рекурсии (помимо всего вышесказанного) в том, что она возвращает результат непосредственно в точку вызова функции, при использовании хвостовой рекурсии не происходит "забивание" стека адресами возврата, поэтому переполнение стека не возможно по определению. На языках С/С++ адрес возврата кладется на стек при каждом вызове функции, т.е. пример выше все же может привести к переполнению стека, а возвращаемое значение пройдет через все вызовы функции. Таким образом т.н. хвостовая рекурсия невозможно на языках С/С++ в силу организации языка. Может быть компилятор сможет ее оптимизировать до "настоящей" хвостовой рекурсии, но это ни где не прописано и ни кем не гарантированно.

Вот такой пример вылетает из-за переполнения стека
C++
1
2
3
4
5
6
7
8
9
10
int f (int n)
{
  if (n == -1) return n;
  return f(++n);
}
 
int main()
{
  f(0);  
}
хотя свиду это та самая хвостовая рекурсия.
Bash
1
2
3
 g++ -O0 tmp.cpp 
 ./a.out 
Segmentation fault (core dumped)
Pure
 Аватар для Pure
228 / 49 / 2
Регистрация: 13.03.2012
Сообщений: 453
Записей в блоге: 7
10.08.2013, 15:06     Чем отличается хвостовая рекурсия от обычной рекурсии? #9
Цитата Сообщение от Kastaneda Посмотреть сообщение
Таким образом т.н. хвостовая рекурсия невозможно на языках С/С++ в силу организации языка
Все возможно

в нашем случае для хвостовой рекурсии нужны именно 2 функции. убираем вызывающую и все никакого хвоста, переполнение, казалось бы с теми ж параметрами.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.08.2013, 18:00     Чем отличается хвостовая рекурсия от обычной рекурсии? #10
Цитата Сообщение от Pure Посмотреть сообщение
Дык тыж сам там написал
компилятор оптимизирует вызовы обращая их в цикл. стек не переполняется
т.е. можно лишь надеяться на то, что твой компилятор сделает именно так. А если это не оптимизирущий компилятор?
Мой пост выше говорит о том, что в некоторых языках хвостовая рекурсия является частью языка, но в С/С++(и многих других процедурных яп) нет.

Добавлено через 1 минуту
перечитал свой пост, оказывается я там же написал
Цитата Сообщение от Kastaneda Посмотреть сообщение
Может быть компилятор сможет ее оптимизировать до "настоящей" хвостовой рекурсии, но это ни где не прописано и ни кем не гарантированно.
Pure
 Аватар для Pure
228 / 49 / 2
Регистрация: 13.03.2012
Сообщений: 453
Записей в блоге: 7
10.08.2013, 18:25     Чем отличается хвостовая рекурсия от обычной рекурсии? #11
Цитата Сообщение от Kastaneda Посмотреть сообщение
лишь надеяться
реальность такова, что вполне себе оптимизирует и мс и гцц. Так и в тех языках ЕСЛИ убрать оптимизацию - как свойство компилятора - то тоже самое и будет
Цитата Сообщение от Kastaneda Посмотреть сообщение
но в С/С++(и многих других процедурных яп) нет.
с чего взял то?

Какие тебе нужны еще компиляторы ++, кроме (мс и гсс) чтобы ты уверовал, что при соблюдении условий хвостовой она будет оптимизирована? Тебе не нравится что это происходит?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.08.2013, 18:35     Чем отличается хвостовая рекурсия от обычной рекурсии? #12
Цитата Сообщение от Pure Посмотреть сообщение
Так и в тех языках ЕСЛИ убрать оптимизацию - как свойство компилятора - то тоже самое и будет
Честно говоря "тех других" я не знаю, но знаю, что среди них есть не компилируемые (интерпретируемые), что помогает им в организации хвостовой рекурсии.
Цитата Сообщение от Pure Посмотреть сообщение
Тебе не нравится что это происходит?
Да почему, нравится.
Цитата Сообщение от Pure Посмотреть сообщение
Какие тебе нужны еще компиляторы ++ чтобы ты уверовал, что при соблюдении условий хвостовой она будет оптимизирована?
Ты можешь гарантировать, что любой компилятор это сделает? Если это не прописано в стандарте (а это не прописано), то нельзя утверждать, что в С++ есть хвостовая рекурсия. GCC позволяет брать адреса меток, можно ли после этого сказать, что С++ позволяет брать адреса меток? Или что в С++ есть case range? (это когда в switch можно писать case 1 ... 10:, как в gcc) ?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2013, 19:19     Чем отличается хвостовая рекурсия от обычной рекурсии? #13
Цитата Сообщение от Kastaneda Посмотреть сообщение
Таким образом т.н. хвостовая рекурсия невозможно на языках С/С++ в силу организации языка.
Непонятно, откуда такой вывод.
Мне кажется, что вы путаете хвостовую рекурсию с оптимизацией хвостовой рекурсии.
Ваш пример, очевидно, является хвостовой рекурсией, но компилятор просто не проводит ее оптимизацию (он вообще не проводит никакие оптимизации, так как -O0). Вот с -O2 он все прекрасно оптимизирует.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 19:35     Чем отличается хвостовая рекурсия от обычной рекурсии?
Еще ссылки по теме:

Рекурсия без рекурсии C++
Чем C++ отличается от C++ Builder? C++
C++ Чем отличается if от (?:)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4237 / 2770 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
10.08.2013, 19:35     Чем отличается хвостовая рекурсия от обычной рекурсии? #14
Цитата Сообщение от diagon Посмотреть сообщение
Мне кажется, что вы путаете хвостовую рекурсию с оптимизацией хвостовой рекурсии.
Мне уже начинает казаться, что я чего-то непонимаю
Хорошо, зайдем с другого бока - что есть хвостовая рекурсия?

Добавлено через 10 минут
Цитата Сообщение от Kastaneda Посмотреть сообщение
Хорошо, зайдем с другого бока - что есть хвостовая рекурсия?
Погуглил, да, признаю, я попутал оптимизацию хвостовой рекурсии и хвостовую рекурсию как таковую. Попутал потому что о хвостовой рекурсии я когда-то узнал из функциональных языков, где ее оптимизация является обязательной (т.е. является частью языка). Поэтому я считал, что суть хвостовой рекурсии как раз и заключается в том, что она оптимизируется. Оказывается это не так. Исходя из определения хвостовой рекурсии можно сказать, что на С/С++, конечно же, можно ее написать и компилятору даже не обязательно ее оптимизировать, чтоб она считалась хвостовой. Т.е. хвостовая рекурсия с переполнением стека вполне может называться хвостовой, чего я никак не ожидал
Yandex
Объявления
10.08.2013, 19:35     Чем отличается хвостовая рекурсия от обычной рекурсии?
Ответ Создать тему
Опции темы

Текущее время: 21:40. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru