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

@AzaKendler · Регистрация: 30.05.2011

Author24 — интернет-сервис помощи студентам

на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз. А как это реализованно в с++? то же с повторениями?
И как выделяется память под рекусивный вызов? Например есть функция с набором локальных переменных - они будут жить до тех пор пока не завершится функция, т.е. так долго пока не будет выход из рекурсии? и мы будем иметь большое множество участков в памяти с одинакововой структурой данных(но разными значениями)?

@~~LosAngeles~~ · 02.09.2011, 18:54

в С++ можно очень быстро выйти из рекурсии выбросив исключение. Ну например при рекурсивном поиске, не будет цепочки ретурнов

@AzaKendler · 02.09.2011, 18:56 **[ТС]**

LosAngeles, а повторы есть? неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?

@grizlik78 · 02.09.2011, 19:00

Дерево похоже на вычисление чисел Фибоначчи. Да повторы будут. Это хорошо видно вот в этой задаче про бесконечные последовательности.

@diagon · 02.09.2011, 19:00

Сообщение от AzaKendler

неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?

А как это обойти можно? =\ Растет конечно, вот пример.

LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более. Даже goto лучше будет. Но гораздо красивее просто цепочка return(а кроме красоты у рекурсии преимуществ мало).

Евгений М. · 02.09.2011, 19:00

Сообщение от AzaKendler

и рекурсия вызывает лавинообразный рост расчета одних и тех же значений?

В зависимости как эта рекурсия реализована. Например, если в реализации запоминается результат, то все на так уж лавинообразно.

@~~LosAngeles~~ · 02.09.2011, 19:14

в общем случае нет никаких повторов, не понимаю о чём ты. Просто слишком велики издержки на вызов функций и в конце придётся кучу ретурнов пройти и если задача сводится к поиску чего-либо, то это как я говорил решается с помощью throw. Вообщем рекурсия медленее итераций и больше жрёт стека

Добавлено через 13 минут

Сообщение от diagon

LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более.

страуструп с тобой не согласен(последнее специальное издание), в стандарте нигде не указано, что исключения нужны только для ошибок и я не раз видел подобный метод в действии. Слово создателя языка и личный опыт для меня как то поавторитетнее будет. А goto использовать неполучится

The goto statement unconditionally transfers control to the statement labeled by the identiﬁer. The identiﬁer shall be a label (6.1) located in the current function.

@diagon · 02.09.2011, 19:18

Сообщение от LosAngeles

страуструп с тобой не согласен(последнее специальное издание), в стандарте нигде не указано, что исключения нужны только для ошибок и я не раз видел подобный метод в действии. Слово создателя языка и личный опыт для меня как то поавторитетнее будет. А goto использовать неполучится

Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.
Ален Голуб, "Веревка достаточной длины, чтобы прострелить себе ногу" - начиная от 159 пункта.

@~~LosAngeles~~ · 02.09.2011, 19:23

Сообщение от diagon

Да, с goto погорячился, но генерация исключений не для ошибки - плохой стиль.

ну так и напиши Бьёрну, что он такой казёл плохому учит

@AzaKendler · 02.09.2011, 19:26 **[ТС]**

LosAngeles, да видимо по сути своей она так организована что повторяется в вычислениях если их не сохранить как в примерах выше.
вопрос

C++

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

Не по теме:

Сообщение от LosAngeles

ну так и напиши Бьёрну, что он такой казёл плохому учит

А можно узнать соответствующий параграф в справочнике? =\ Просто мне кажется, что там написано, что исключения могут быть использованы в нестандартных ситуациях, т.е. что язык это позволяет, но что он рекомендует использовать подобное - не верю.
P.S. цепочка return еще и эффективнее должна быть.

Обработка исключения вызывает
очень большие непроизводительные затраты, выражающиеся в возрастании в несколько раз размера
кода и времени выполнения. Это происходит даже в операционных системах типа Microsoft NT,
которая поддерживает обработку исключений на уровне операционной системы. Вы можете
рассчитывать на 10-20% увеличение размера кода и падение скорости выполнения на несколько
процентов при интенсивном использовании исключений.
----
Следовательно, исключения должны
использоваться лишь тогда, когда непроизводительные затраты не берутся в расчет, обычно при
наличии возможности лучше предпочесть возврат ошибки.

(с) Ален Голуб

@~~LosAngeles~~ · 02.09.2011, 19:36

14.1.1 страница 410

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

Добавлено через 2 минуты
вот именно в ней и говорится что исключения стоит применять в глубоко рекурсивных функциях поиска, например по дереву. Цитирую: "элегантный способ"

@AzaKendler · 02.09.2011, 19:37 **[ТС]**

хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw

@Thinker · 02.09.2011, 19:39

Сообщение от AzaKendler

на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз.

Вообще все зависит от задачи и от реализации. Если рекурсия для линейных структур, то вполне можно без повторений обойтись. Если рекуррентное соотношение предполагает повторения, то лучше без нее (рекурсии) обойтись.

@~~LosAngeles~~ · 02.09.2011, 19:39

никак

@Thinker · 02.09.2011, 19:43

Сообщение от AzaKendler

хорошо, как подняться с большой глубины рекурсии минуя цепь return?
кроме throw

Если функция ничего не возвращает, то достижение окончания функции, но это как просто return;

@AzaKendler · 02.09.2011, 19:45 **[ТС]**

Thinker, вот в чем дело. подозреваю что из за повторных вычислений я получаю на выходе некое неверное значение. тот пример что я привел - постарался выразить некие опасения, есть в таком варианте повторы или нет? рекурсия в цикле. И вообще мож это в корне неверно мешать одно с другим? В том примере выход из рекурсии - когда вектор пуст. После этого начнутся return

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

Сообщение от Thinker

но это как просто return

т.е просто по цепочке вверх пойдет, верно? последовательно вверх.

А как это все лежит в памяти, что с автопеременными, когда я ушел вглубь из функции?

@~~LosAngeles~~ · 02.09.2011, 19:47

от старших адресов к младшим. Чем глубже тем младше адрес, это же стек

@Thinker · 02.09.2011, 19:49

Сообщение от AzaKendler

подозреваю что из за повторных вычислений я получаю на выходе некое неверное значение.

Это (повторы) на результат никак не влияет. Все зависит от правильности организации алгоритма.

Сообщение от AzaKendler

И вообще мож это в корне неверно мешать одно с другим?

В рекурсии может присутствовать сколько угодно циклов.

Сообщение от AzaKendler

т.е просто по цепочке вверх пойдет, верно? последовательно вверх.
А как это все лежит в памяти, что с автопеременными, когда я ушел вглубь из функции?

Пойдет вверх. Также, как и обычная загрузка функции в стек.

@AzaKendler · 02.09.2011, 19:49 **[ТС]**

LosAngeles, логично и автопеременные живут каким то образом. получается динамическое заполнение стэка? Для каждого вызова в глубь новый адрес под тело?

@~~LosAngeles~~ Заблокирован
	02.09.2011, 19:36	12
	14.1.1 страница 410 Добавлено через 1 минуту и 14.5 страница 427 Добавлено через 2 минуты вот именно в ней и говорится что исключения стоит применять в глубоко рекурсивных функциях поиска, например по дереву. Цитирую: "элегантный способ" 0

@Thinker 4267 / 2241 / 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, 18:54	2
	в С++ можно очень быстро выйти из рекурсии выбросив исключение. Ну например при рекурсивном поиске, не будет цепочки ретурнов 0

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	02.09.2011, 18:56 [ТС]	3
	LosAngeles, а повторы есть? неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений? 0

@grizlik78 2381 / 1665 / 279 Регистрация: 29.05.2011 Сообщений: 3,399
	02.09.2011, 19:00	4
	Дерево похоже на вычисление чисел Фибоначчи. Да повторы будут. Это хорошо видно вот в этой задаче про бесконечные последовательности. 1

@diagon Higher 1953 / 1219 / 120 Регистрация: 02.05.2010 Сообщений: 2,925 Записей в блоге: 2
	02.09.2011, 19:00	5
	Сообщение от AzaKendler неужто не обошли это и рекурсия вызывает лавинообразный рост расчета одних и тех же значений? А как это обойти можно? =\ Растет конечно, вот пример. LosAngeles, исключения нужны, чтобы оповещать о ошибке, не более. Даже goto лучше будет. Но гораздо красивее просто цепочка return(а кроме красоты у рекурсии преимуществ мало). 2

Евгений М. 1080 / 1007 / 106 Регистрация: 28.02.2010 Сообщений: 2,889
	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 identiﬁer. The identiﬁer shall be a label (6.1) located in the current function. 1

@diagon Higher 1953 / 1219 / 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

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

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772
	02.09.2011, 19:37 [ТС]	13
	хорошо, как подняться с большой глубины рекурсии минуя цепь return? кроме throw 0

	02.09.2011, 19:49

@Thinker 4267 / 2241 / 203 Регистрация: 26.08.2011 Сообщений: 3,802 Записей в блоге: 5
	02.09.2011, 19:39	14
	Сообщение от AzaKendler на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз. Вообще все зависит от задачи и от реализации. Если рекурсия для линейных структур, то вполне можно без повторений обойтись. Если рекуррентное соотношение предполагает повторения, то лучше без нее (рекурсии) обойтись. 0

@~~LosAngeles~~ Заблокирован
	02.09.2011, 19:39	15
	никак 0

@~~LosAngeles~~ Заблокирован
	02.09.2011, 19:47	18
	от старших адресов к младшим. Чем глубже тем младше адрес, это же стек 1

@Thinker 4267 / 2241 / 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

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

Решение