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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.90
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
#1

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

02.09.2011, 18:49. Просмотров 1471. Ответов 24
Метки нет (Все метки)

на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз. А как это реализованно в с++? то же с повторениями?
И как выделяется память под рекусивный вызов? Например есть функция с набором локальных переменных - они будут жить до тех пор пока не завершится функция, т.е. так долго пока не будет выход из рекурсии? и мы будем иметь большое множество участков в памяти с одинакововой структурой данных(но разными значениями)?
0
Миниатюры
Рекурсия  
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.09.2011, 18:49
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Рекурсия (C++):

Рекурсия - C++
Здравствуйте, писали на лабораторной программу с использованием рекурсии, о бъясните почему в ответе двойки выдает?? и что рекурсивная...

Рекурсия - C++
Помогите пожалуйста составить программу, с помощью рекурсии: Определить значение отношения максимального и минимального из...

рекурсия на с - C++
разработать рекурсивную функцию для вычитания двух подлинных двоичных чисел, заданных в виде символьных строк. разрядность цифр может быть...

Рекурсия - C++
Всем доброго времени суток! Прошу Вашей помощи! Задание такого: Вычислить, используя рекурсию, выражение: //и вот собственно...

Рекурсия - C++
Привет, помогите пожалуйста надо вычислить рекурсивную функцию : (x+a(x+(a-1)(x+(a-2)(x+...2(x+1)^2)^2)^2)^2)^2. Помогите пожалуйста ,...

Рекурсия - C++
Задан массив целых чисел: а0, а1 ..., аn-1. Известно, что один из элементов массива принимает нулевое значение. Найти номер данного...

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

LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более. Даже goto лучше будет. Но гораздо красивее просто цепочка return(а кроме красоты у рекурсии преимуществ мало).
2
Евгений М.
1047 / 986 / 58
Регистрация: 28.02.2010
Сообщений: 2,858
Завершенные тесты: 2
02.09.2011, 19:00 #6
Цитата Сообщение от AzaKendler Посмотреть сообщение
и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?
В зависимости как эта рекурсия реализована. Например, если в реализации запоминается результат, то все на так уж лавинообразно.
1
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.
1
diagon
Higher
1936 / 1202 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
02.09.2011, 19:18 #8
Цитата Сообщение от LosAngeles Посмотреть сообщение
страуструп с тобой не согласен(последнее специальное издание), в стандарте нигде не указано, что исключения нужны только для ошибок и я не раз видел подобный метод в действии. Слово создателя языка и личный опыт для меня как то поавторитетнее будет. А goto использовать неполучится
Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.
Ален Голуб, "Веревка достаточной длины, чтобы прострелить себе ногу" - начиная от 159 пункта.
1
LosAngeles
Заблокирован
02.09.2011, 19:23 #9
Цитата Сообщение от diagon Посмотреть сообщение
Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.
ну так и напиши Бьёрну, что он такой казёл плохому учит
0
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;
 }
это рекурсия? если да то будут ли повторения? как избежать?
0
diagon
02.09.2011, 19:27
  #11

Не по теме:

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

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

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

Добавлено через 2 минуты
вот именно в ней и говорится что исключения стоит применять в глубоко рекурсивных функциях поиска, например по дереву. Цитирую: "элегантный способ"
0
AzaKendler
214 / 116 / 9
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:37  [ТС] #13
хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw
0
Thinker
Эксперт С++
4231 / 2205 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:39 #14
Цитата Сообщение от AzaKendler Посмотреть сообщение
на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз.
Вообще все зависит от задачи и от реализации. Если рекурсия для линейных структур, то вполне можно без повторений обойтись. Если рекуррентное соотношение предполагает повторения, то лучше без нее (рекурсии) обойтись.
0
LosAngeles
Заблокирован
02.09.2011, 19:39 #15
никак
0
02.09.2011, 19:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.09.2011, 19:39
Привет! Вот еще темы с ответами:

рекурсия - C++
Сделать рекурсию, кроме факториала!

Рекурсия - C++
Вопрос не по коду. Вот есть у меня рекурсивная функция, глубина рекурсии достигает 10 в среднем. Эта функция вызывается огромное (порядка...

Рекурсия - C++
Есть задача, написал решение но ответ неправильный. Задача: Решение: #include &lt;iostream&gt; using namespace std; int a, n, m, t,...

рекурсия - C++
Доброго времени суток. Уважаемые ГУРУ, есть одна проблема. Ниже представлен код, в котором параметр b должен быть всегда...


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

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

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