Как предотвратить ненужное использование памяти в рекурсивных функциях

Question

Я только что написал рекурсивную функцию, и до меня дошло, что все переменные, которые я использую внутри функции, будут оставаться в памяти до тех пор, пока не прервется рекурсия.Если я повторяю большое количество раз или выделяю большие объемы памяти для переменных, не используемых в последующем вызове рекурсивной функции, может ли это привести к значительному расточительному использованию памяти?* используется в следующем рекурсе, а temp_int и temp_vec будут продолжать занимать память без необходимости.

int recurse(std::vector<int> arg_vec) {
  int temp_int i;

  std::vector<int> temp_vec;
  std::vector<int> vec2;

  //... do some processing with arg_vec and temp_vec and result is stored in vec2
  recurse(vec2)

  return if (some condition met);
}

Должен ли я тогда выделять всю память, используя новые команды, и удалять их перед вызовом функции?Или есть какой-то другой способ справиться с этим

Answer 1

Вы можете использовать скобки области, чтобы указать область.Все, что объявлено в области видимости, уничтожается в конце области.

int recurse(std::vector<int> arg_vec) {
  int temp_int i;

  std::vector<int> vec2;
  {
    std::vector<int> temp_vec;

    //... do some processing with arg_vec and temp_vec and result is stored in vec2
  } // temp_vec is destructed here. vec2 is not because it is outside this scope.
  recurse(ec2)

  return if (some condition met);
}

Answer 2

Обычно в этой ситуации вы делаете хвостовую рекурсию , которая позволяет компилятору оптимизировать именно это.

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

Редактировать (уточнение)

int foo(int i) {
  if (stop_condition(i))
    return stuff;
  // fancy computation
  return foo(bar);
}

Answer 3

Приложения, как правило, имеют больше кучи памяти, чем стек, поэтому вы можете выделить их вместо использования автоматического хранения.Это то, что вы уже делаете, когда используете std :: vector.Распределение может быть медленным, хотя.Чтобы получить лучшее из обоих миров, перепишите свою рекурсивную функцию, используя вместо этого итерацию.Затем вы можете предварительно выделить один раз и перераспределить в случае использования предварительно выделенного пространства.

Answer 4

Переход на ручное выделение пары std::vector не будет иметь большого значения.Вектор действительно представляет собой довольно небольшую структуру данных (обычно два size_t с плюс один указатель) - хранилище для фактических данных уже выделено динамически.Следовательно, динамическое выделение std::vector может спасти вам всего два size_t на кадр стека.Если вы правы на грани того, что-то работает или нет, это может иметь реальное значение, но я предполагаю, что это довольно редко (и если вы настолько близки, вам, вероятно, следует сначала рассмотреть другие возможности).

Answer 5

Вы МОЖЕТЕ выделить все с новым, но может быть проще переместить код, выполняющий фактическую обработку, в другую функцию со своими собственными локальными объектами.Примерно так:

void subfunction(vector arg_vec, vector result_vec)
{
   int temp_int;
   vector temp_vec;

   // do stuff
   return;
}

int recurse(vector arg_vec) {
   vector vec2;

   subfunction(arg_vec, vec2);
   recurse(vec2);
}

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

Answer 6

Хвостовые вызовы можно оптимизировать так, чтобы они вообще не занимали дополнительного места в стеке, что делает их эффективными для памяти и (примерно, в зависимости от других факторов) быстрыми, как итеративная версия. Все современные компиляторы C и C ++ выполняют эту оптимизацию. И даже если это не хвостовой вызов, компилятор может разработать оптимизированную версию без отказов. В этом ответе кто-то проверенный gcc превратит наивную факториальную реализацию в быструю итерацию даже на -O2.

Answer 7

Вы можете освободить память массива temp_vec перед входом в рекурсию.

Не через

temp_vec.clear();

, поскольку стандарт не гарантирует, что clear () освобождает выделенную память массива

std::swap(temp_vec. std::vector<int>());

В любом случае, использование другой области видимости для temp_vec более полезно в этом примере, поскольку после выхода из области видимости пространство векторного объекта освобождается в стеке. Смотрите другой ответ.

Кстати, рассмотрите вместо использования вызова по значению

int recurse(std::vector<int> arg_vec) {

вызов по ссылке, чтобы избежать ненужного векторного копирования:

int recurse(const std::vector<int> &arg_vec) {