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

Рекурсия - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 18:49     Рекурсия #1
на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз. А как это реализованно в с++? то же с повторениями?
И как выделяется память под рекусивный вызов? Например есть функция с набором локальных переменных - они будут жить до тех пор пока не завершится функция, т.е. так долго пока не будет выход из рекурсии? и мы будем иметь большое множество участков в памяти с одинакововой структурой данных(но разными значениями)?
Миниатюры
Рекурсия  
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.09.2011, 18:49     Рекурсия
Посмотрите здесь:

РЕкурсия C++
Рекурсия (на С) C++
Рекурсия C++
рекурсия C++
Рекурсия C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
LosAngeles
Заблокирован
02.09.2011, 18:54     Рекурсия #2
в С++ можно очень быстро выйти из рекурсии выбросив исключение. Ну например при рекурсивном поиске, не будет цепочки ретурнов
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 18:56  [ТС]     Рекурсия #3
LosAngeles, а повторы есть? неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
02.09.2011, 19:00     Рекурсия #4
Дерево похоже на вычисление чисел Фибоначчи. Да повторы будут. Это хорошо видно вот в этой задаче про бесконечные последовательности.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.09.2011, 19:00     Рекурсия #5
Цитата Сообщение от AzaKendler Посмотреть сообщение
неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?
А как это обойти можно? =\ Растет конечно, вот пример.

LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более. Даже goto лучше будет. Но гораздо красивее просто цепочка return(а кроме красоты у рекурсии преимуществ мало).
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
02.09.2011, 19:00     Рекурсия #6
Цитата Сообщение от AzaKendler Посмотреть сообщение
и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?
В зависимости как эта рекурсия реализована. Например, если в реализации запоминается результат, то все на так уж лавинообразно.
LosAngeles
Заблокирован
02.09.2011, 19:14     Рекурсия #7
в общем случае нет никаких повторов, не понимаю о чём ты. Просто слишком велики издержки на вызов функций и в конце придётся кучу ретурнов пройти и если задача сводится к поиску чего-либо, то это как я говорил решается с помощью throw. Вообщем рекурсия медленее итераций и больше жрёт стека

Добавлено через 13 минут
Цитата Сообщение от diagon Посмотреть сообщение
LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более.
страуструп с тобой не согласен(последнее специальное издание), в стандарте нигде не указано, что исключения нужны только для ошибок и я не раз видел подобный метод в действии. Слово создателя языка и личный опыт для меня как то поавторитетнее будет. А goto использовать неполучится
The goto statement unconditionally transfers control to the statement labeled by the identifier. The identifier shall be a label (6.1) located in the current function.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.09.2011, 19:18     Рекурсия #8
Цитата Сообщение от LosAngeles Посмотреть сообщение
страуструп с тобой не согласен(последнее специальное издание), в стандарте нигде не указано, что исключения нужны только для ошибок и я не раз видел подобный метод в действии. Слово создателя языка и личный опыт для меня как то поавторитетнее будет. А goto использовать неполучится
Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.
Ален Голуб, "Веревка достаточной длины, чтобы прострелить себе ногу" - начиная от 159 пункта.
LosAngeles
Заблокирован
02.09.2011, 19:23     Рекурсия #9
Цитата Сообщение от diagon Посмотреть сообщение
Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.
ну так и напиши Бьёрну, что он такой казёл плохому учит
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:26  [ТС]     Рекурсия #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
LosAngeles, да видимо по сути своей она так организована что повторяется в вычислениях если их не сохранить как в примерах выше.
вопрос

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class A{...};
 
 
int Rekurs(A* a)
{
 
int temp = 0;
temp = a->VAL;
  if(a->BLACK==true)
  {
   vector<A*> RED;//к примеру он наполняется разным количеством А* c RED==true;
 
   for(int i =0;i<RED.size();i++)
     {
     temp+=Rekurs(RED[i]);
     }
  }
  else 
  {
 
   vector<A*> BLACK;//к примеру он наполняется разным количеством А* c BLACK==true
 
    for(int i =0;i<BLACKc.size();i++)
     {
      temp+= Rekurs(BLACK[i]);
     }
 
 
   }
return temp;
 }
это рекурсия? если да то будут ли повторения? как избежать?
diagon
02.09.2011, 19:27
  #11

Не по теме:

Цитата Сообщение от LosAngeles Посмотреть сообщение
ну так и напиши Бьёрну, что он такой казёл плохому учит
А можно узнать соответствующий параграф в справочнике? =\ Просто мне кажется, что там написано, что исключения могут быть использованы в нестандартных ситуациях, т.е. что язык это позволяет, но что он рекомендует использовать подобное - не верю.
P.S. цепочка return еще и эффективнее должна быть.
Обработка исключения вызывает
очень большие непроизводительные затраты, выражающиеся в возрастании в несколько раз размера
кода и времени выполнения. Это происходит даже в операционных системах типа Microsoft NT,
которая поддерживает обработку исключений на уровне операционной системы. Вы можете
рассчитывать на 10-20% увеличение размера кода и падение скорости выполнения на несколько
процентов при интенсивном использовании исключений.
----
Следовательно, исключения должны
использоваться лишь тогда, когда непроизводительные затраты не берутся в расчет, обычно при
наличии возможности лучше предпочесть возврат ошибки.
(с) Ален Голуб

LosAngeles
Заблокирован
02.09.2011, 19:36     Рекурсия #12
14.1.1 страница 410

Добавлено через 1 минуту
и 14.5 страница 427

Добавлено через 2 минуты
вот именно в ней и говорится что исключения стоит применять в глубоко рекурсивных функциях поиска, например по дереву. Цитирую: "элегантный способ"
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:37  [ТС]     Рекурсия #13
хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:39     Рекурсия #14
Цитата Сообщение от AzaKendler Посмотреть сообщение
на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз.
Вообще все зависит от задачи и от реализации. Если рекурсия для линейных структур, то вполне можно без повторений обойтись. Если рекуррентное соотношение предполагает повторения, то лучше без нее (рекурсии) обойтись.
LosAngeles
Заблокирован
02.09.2011, 19:39     Рекурсия #15
никак
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:43     Рекурсия #16
Цитата Сообщение от AzaKendler Посмотреть сообщение
хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw
Если функция ничего не возвращает, то достижение окончания функции, но это как просто return;
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:45  [ТС]     Рекурсия #17
Thinker, вот в чем дело. подозреваю что из за повторных вычислений я получаю на выходе некое неверное значение. тот пример что я привел - постарался выразить некие опасения, есть в таком варианте повторы или нет? рекурсия в цикле. И вообще мож это в корне неверно мешать одно с другим? В том примере выход из рекурсии - когда вектор пуст. После этого начнутся return

Добавлено через 1 минуту
Цитата Сообщение от Thinker Посмотреть сообщение
но это как просто return
т.е просто по цепочке вверх пойдет, верно? последовательно вверх.


А как это все лежит в памяти, что с автопеременными, когда я ушел вглубь из функции?
LosAngeles
Заблокирован
02.09.2011, 19:47     Рекурсия #18
от старших адресов к младшим. Чем глубже тем младше адрес, это же стек
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:49     Рекурсия #19
Цитата Сообщение от AzaKendler Посмотреть сообщение
подозреваю что из за повторных вычислений я получаю на выходе некое неверное значение.
Это (повторы) на результат никак не влияет. Все зависит от правильности организации алгоритма.

Цитата Сообщение от AzaKendler Посмотреть сообщение
И вообще мож это в корне неверно мешать одно с другим?
В рекурсии может присутствовать сколько угодно циклов.

Цитата Сообщение от AzaKendler Посмотреть сообщение
т.е просто по цепочке вверх пойдет, верно? последовательно вверх.
А как это все лежит в памяти, что с автопеременными, когда я ушел вглубь из функции?
Пойдет вверх. Также, как и обычная загрузка функции в стек.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2011, 19:49     Рекурсия
Еще ссылки по теме:

C++ Рекурсия
C++ Рекурсия
Рекурсия C++

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

Или воспользуйтесь поиском по форуму:
AzaKendler
 Аватар для AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:49  [ТС]     Рекурсия #20
LosAngeles, логично и автопеременные живут каким то образом. получается динамическое заполнение стэка? Для каждого вызова в глубь новый адрес под тело?
Yandex
Объявления
02.09.2011, 19:49     Рекурсия
Ответ Создать тему
Опции темы

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