How to prevent unnecessary memory use in recursive functions

Question

I've just written a recursive function and it dawned on me that all the variables I use within the function will remain allocated in memory until recursion breaks. If I am recursing a large number of times or allocating large amounts of memory for variables not used in the consequent recursive function call, could this lead to alot of wasteful memory use?

E.g. in the following, only vec2 is used in the following recurse and temp_int and temp_vec will continue to occupy memory needlessly.

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);
}

Should I then be allocating all memory using the new commands and deleting them before the function call? Or is there some other method for dealing with this

Answer 1

You can use scope braces to specify a scope. Anything declared in a scope is destroyed at the end of the scope.

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

Typically, what you do in this situation is tail-recursion, which allows the compiler to optimise just that.

That means, the last thing your recursive function does is calling itself. I am not aware how good the optimisation is if you have further instructions.

Edit (clarification)

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

Answer 3

You could free the array-memory of temp_vec before entering the recursion.

Not via

temp_vec.clear();

since the standard does not guarantees that clear() frees the allocated array memory

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

Anyways, using another scope for temp_vec is more useful in that example, since after leaving the scope the space of the vector object itself is freed on the stack. See the other answer.

Btw, consider instead of using call-by-value

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

call by reference to avoid unnecessary vector copying:

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

Answer 4

Applications tend to have more heap memory than stack, so you could allocate instead of using automatic storage. This is what you're already doing when you use std::vector. Allocation can be slow though. To get the best of both worlds, rewrite your recursive function by using iteration instead. Then you can pre-allocate once, and re-allocate in the event you use up the preallocated space.

Answer 5

Tail calls can be optimized to consume no additional stack space at all, making them as memory-effective and (circa, depending on other factores) fast as the iterative version. All modern C and C++ compilers perform this optimization. And even if it is not a tail call, the compiler may work out an optimized version without recusion. In this answer, someone proofed gcc will turn a naive factorial implementation in a fast iteration even on -O2.

Answer 6

You COULD allocate everything with new, but it might be easier to move the code doing the actual processing into another function with its own locals. Something like this:

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);
}

As a bonus, now you're halfway to turning the recursion into a loop, which is a better way to handle things if you're recursing enough that stack space might be an issue.

Answer 7

Changing to manually allocating a couple of std::vectors isn't going to make much difference. A vector is really a pretty small data structure (typically two size_ts plus one pointer) -- the storage for the actual data is allocated dynamically already. Therefore, allocating an std::vector dynamically is only likely to save you something like two size_ts per stack frame. If you're right on the ragged edge of something working or not, that might make a real difference, but I'd guess it's pretty rare (and if you are that close, you should probably be looking at other possibilities first).