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

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

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

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

@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++
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

Не по теме:

Сообщение от 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, логично и автопеременные живут каким то образом. получается динамическое заполнение стэка? Для каждого вызова в глубь новый адрес под тело?

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .
SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15

	Рекурсия: как выделяется память под рекурсивный вызов? 02.09.2011, 18:49. Показов 9438. Ответов 24 Метки нет (Все метки) на картинке файлик из википедии в которой говорится что рекусия имеет вид дерева и некоторые ветви могут вычислятся по многу раз. А как это реализованно в с++? то же с повторениями? И как выделяется память под рекусивный вызов? Например есть функция с набором локальных переменных - они будут жить до тех пор пока не завершится функция, т.е. так долго пока не будет выход из рекурсии? и мы будем иметь большое множество участков в памяти с одинакововой структурой данных(но разными значениями)? Миниатюры 0

@LosAngeles Заблокирован
	02.09.2011, 18:54
	в С++ можно очень быстро выйти из рекурсии выбросив исключение. Ну например при рекурсивном поиске, не будет цепочки ретурнов 0

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

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

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

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

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

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

@AzaKendler 214 / 116 / 14 Регистрация: 30.05.2011 Сообщений: 1,772 Записей в блоге: 15
	02.09.2011, 19:49 [ТС]
	LosAngeles, логично и автопеременные живут каким то образом. получается динамическое заполнение стэка? Для каждого вызова в глубь новый адрес под тело? 0

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

Решение