Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 63, средняя оценка - 4.81
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
#1

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

10.01.2013, 22:15. Просмотров 9929. Ответов 13
Метки нет (Все метки)

Собственно вопрос сверху. Если не затруднит, то покажите пример факториала с хвостовой и с обычной рекурсией. Буду крайне благодарен.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2013, 22:15
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Чем отличается хвостовая рекурсия от обычной рекурсии? (C++):

Хвостовая рекурсия - C++
int fac_times (int n, int acc) { if (n == 0) return acc; else return fac_times(n - 1, acc * n); } int factorial (int n)...

Быстрая сортировка и хвостовая рекурсия(как реализовать?) - C++
Как реализовать хвостовую рекурсию в быстрой сортировке? К примеру вот программа быстрого поиска: void qsort (int b, int e) { ...

Рекурсия от рекурсии - C++
Люди, помогите! Я в с++ относительно недавно, в паскале-делфи никаких проблем не было. Значит мне нужно: int pekypc() { ... ...

Рекурсия без рекурсии - C++
Как известно с рекурсией связана маленькая скорость и проблема переполнения стека. Ее можно сымитировать с помощью обычного стека. ...

Чем отличается if от (?:) - C++
Здравствуйте. Почитываю С++, сам программирую в Делфи. Вот немного запутался. В делфи есть условный оператор if, тогда как в С++ есть такой...

Чем отличается this от *this? - C++
Привет всем ! вот код template<typename Key, typename Value> Dictionary<Key, Value>& Dictionary<Key, Value>::operator =(const...

13
Croessmah
Ушел
13770 / 8020 / 924
Регистрация: 27.09.2012
Сообщений: 19,747
Записей в блоге: 3
Завершенные тесты: 1
10.01.2013, 22:25 #2
Цитата Сообщение от aleksand Посмотреть сообщение
Если не затруднит, то покажите пример факториала с хвостовой и с обычной рекурсией.
Хвостовая рекурсия
Есть пример как раз для факториала
1
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);
}
0
Croessmah
Ушел
13770 / 8020 / 924
Регистрация: 27.09.2012
Сообщений: 19,747
Записей в блоге: 3
Завершенные тесты: 1
10.01.2013, 22:55 #4
Цитата Сообщение от aleksand Посмотреть сообщение
но понять не могу где здесь рекурсивный вызов функцией самой себя является её последней операцией?
C++
1
return fac_times(n - 1, acc * n);
И в той же статье рядом код не хвостовой рекурсии:
C++
1
return n * factorial(n - 1);
Найдите отличия =)
1
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
10.01.2013, 23:53  [ТС] #5
Цитата Сообщение от Croessmah Посмотреть сообщение
И в той же статье рядом код не хвостовой рекурсии:
C++
1
return n * factorial(n - 1);
Найдите отличия =)
Кажется понял, отличие в том, что в хвостовой последнее что делается в коде это делается вызов рекурсии(именно её одной без всяких там умножений, делений и тому прочего), а в нехвостовой как раз-таки делается что-то добавочное к рекурсивному вызову. Верно я всё понял?
0
Croessmah
Ушел
13770 / 8020 / 924
Регистрация: 27.09.2012
Сообщений: 19,747
Записей в блоге: 3
Завершенные тесты: 1
10.01.2013, 23:56 #6
Цитата Сообщение от aleksand Посмотреть сообщение
Верно я всё понял?
Собственно, в той статье в википедии написано:
Стоит отметить, что другой, более естественный рекурсивный способ вычисления факториала, приведённый ниже, не является хвостово-рекурсивным, так как в каждом вызове функции после рекурсивного вызова производятся дополнительные операции, а именно умножение на n.
2
aleksand
21 / 9 / 2
Регистрация: 18.06.2011
Сообщений: 185
11.01.2013, 00:01  [ТС] #7
Цитата Сообщение от Croessmah Посмотреть сообщение
Собственно, в той статье в википедии написано:
Спасибо, разобрался. Что-то под вечер совсем голова не работает видимо.
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 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)
2
Pure
228 / 49 / 2
Регистрация: 13.03.2012
Сообщений: 453
Записей в блоге: 7
10.08.2013, 15:06 #9
Цитата Сообщение от Kastaneda Посмотреть сообщение
Таким образом т.н. хвостовая рекурсия невозможно на языках С/С++ в силу организации языка
Все возможно

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

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

Какие тебе нужны еще компиляторы ++, кроме (мс и гсс) чтобы ты уверовал, что при соблюдении условий хвостовой она будет оптимизирована? Тебе не нравится что это происходит?
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
10.08.2013, 18:35 #12
Цитата Сообщение от Pure Посмотреть сообщение
Так и в тех языках ЕСЛИ убрать оптимизацию - как свойство компилятора - то тоже самое и будет
Честно говоря "тех других" я не знаю, но знаю, что среди них есть не компилируемые (интерпретируемые), что помогает им в организации хвостовой рекурсии.
Цитата Сообщение от Pure Посмотреть сообщение
Тебе не нравится что это происходит?
Да почему, нравится.
Цитата Сообщение от Pure Посмотреть сообщение
Какие тебе нужны еще компиляторы ++ чтобы ты уверовал, что при соблюдении условий хвостовой она будет оптимизирована?
Ты можешь гарантировать, что любой компилятор это сделает? Если это не прописано в стандарте (а это не прописано), то нельзя утверждать, что в С++ есть хвостовая рекурсия. GCC позволяет брать адреса меток, можно ли после этого сказать, что С++ позволяет брать адреса меток? Или что в С++ есть case range? (это когда в switch можно писать case 1 ... 10:, как в gcc) ?
0
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
10.08.2013, 19:19 #13
Цитата Сообщение от Kastaneda Посмотреть сообщение
Таким образом т.н. хвостовая рекурсия невозможно на языках С/С++ в силу организации языка.
Непонятно, откуда такой вывод.
Мне кажется, что вы путаете хвостовую рекурсию с оптимизацией хвостовой рекурсии.
Ваш пример, очевидно, является хвостовой рекурсией, но компилятор просто не проводит ее оптимизацию (он вообще не проводит никакие оптимизации, так как -O0). Вот с -O2 он все прекрасно оптимизирует.
0
Kastaneda
Jesus loves me
Эксперт С++
4749 / 2953 / 242
Регистрация: 12.12.2009
Сообщений: 7,493
Записей в блоге: 2
Завершенные тесты: 1
10.08.2013, 19:35 #14
Цитата Сообщение от diagon Посмотреть сообщение
Мне кажется, что вы путаете хвостовую рекурсию с оптимизацией хвостовой рекурсии.
Мне уже начинает казаться, что я чего-то непонимаю
Хорошо, зайдем с другого бока - что есть хвостовая рекурсия?

Добавлено через 10 минут
Цитата Сообщение от Kastaneda Посмотреть сообщение
Хорошо, зайдем с другого бока - что есть хвостовая рекурсия?
Погуглил, да, признаю, я попутал оптимизацию хвостовой рекурсии и хвостовую рекурсию как таковую. Попутал потому что о хвостовой рекурсии я когда-то узнал из функциональных языков, где ее оптимизация является обязательной (т.е. является частью языка). Поэтому я считал, что суть хвостовой рекурсии как раз и заключается в том, что она оптимизируется. Оказывается это не так. Исходя из определения хвостовой рекурсии можно сказать, что на С/С++, конечно же, можно ее написать и компилятору даже не обязательно ее оптимизировать, чтоб она считалась хвостовой. Т.е. хвостовая рекурсия с переполнением стека вполне может называться хвостовой, чего я никак не ожидал
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.08.2013, 19:35
Привет! Вот еще темы с ответами:

Чем отличается ln , lg, и log ? - C++
и как реализуются эти функцию в c++

Чем new отличается от malloc? - C++
Чем new отличается от malloc?

Чем отличается С++ от Visual С++? - C++
Здравствуете товарищи программисты! Только начал изучать язык программирования С++ и возникло пару вопросов. Чем отличается С++ от Visual...

Чем C++ отличается от C++ Builder? - C++
Чем C++ отличается от C++ Builder? И если имеется желание писать именно в C++, а не в билдере, то что для этого ещё надо освоить и каким...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru