Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 5.00/8: Рейтинг темы: голосов - 8, средняя оценка - 5.00
AzaKendler
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
1

Рекурсия: как выделяется память под рекурсивный вызов?

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

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

Как выделяется память под массив string?
В общем читаю книжку, там объявлены два массива int* p = new int, int* v = new string... бла бла...

Объясните как выделяется память под умные указатели
Читаю книгу Праты, не могу понять этот абзац, а точнее применение операторов new и new и delete и...

Почему не выделяется память под двумерный массив?
**ptrarray = new float* ; for (int i = 0; i < h; i++){ ptrarray = new float ; } ...

Как выделяется память на стеке и на куче? Когда нужна ручная очистка?
Всем здрасьте. //1 char s = 's'; //2 char* ss = new char; Во втором случае компилятор...

Выделить память под двумерный массив за один вызов функции malloc
Выделить память под двумерный массив за один вызов функции malloc Если можно - с комментариями

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

LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более. Даже goto лучше будет. Но гораздо красивее просто цепочка return(а кроме красоты у рекурсии преимуществ мало).
2
Евгений М.
1053 / 990 / 101
Регистрация: 28.02.2010
Сообщений: 2,876
Завершенные тесты: 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
1937 / 1203 / 120
Регистрация: 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 / 14
Регистрация: 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 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:37  [ТС] 13
хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:39 14
Цитата Сообщение от AzaKendler Посмотреть сообщение
на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз.
Вообще все зависит от задачи и от реализации. Если рекурсия для линейных структур, то вполне можно без повторений обойтись. Если рекуррентное соотношение предполагает повторения, то лучше без нее (рекурсии) обойтись.
0
LosAngeles
Заблокирован
02.09.2011, 19:39 15
никак
0
Thinker
Эксперт С++
4232 / 2206 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.09.2011, 19:43 16
Цитата Сообщение от AzaKendler Посмотреть сообщение
хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw
Если функция ничего не возвращает, то достижение окончания функции, но это как просто return;
0
AzaKendler
214 / 116 / 14
Регистрация: 30.05.2011
Сообщений: 1,772
02.09.2011, 19:45  [ТС] 17
Thinker, вот в чем дело. подозреваю что из за повторных вычислений я получаю на выходе некое неверное значение. тот пример что я привел - постарался выразить некие опасения, есть в таком варианте повторы или нет? рекурсия в цикле. И вообще мож это в корне неверно мешать одно с другим? В том примере выход из рекурсии - когда вектор пуст. После этого начнутся return

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


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

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

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

Не выделяется память
Здравствуйте, пытаюсь выделить память, на одном компьютере работает, на другом нет, возвращает...

Выделяется ли память?
Доброе время суток! У меня есть BYTE *pOutData = NULL; Объясните пожалуйста что происходит в...

Не выделяется память
#include&lt;iostream&gt; #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; using namespace std; class DynArray {...


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

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

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