Recursive memory-optimized calls in C

Question

I have a recursive function that can be written like this:

void func(TypeName *dataStructure, LL_Node **accumulator) { func(datastructure->left, accumulator); func(datastructure->right, accumulator); { char buffer[1000]; // do some stuff } return; } 

I know that in fact the buffer is allocated at the beginning of the function and puts the statement in the block of the nested area, in fact, does not use the new stack frame . But I do not want the compiler to allocate an exponential number of 1000-byte buffers at a time when they can be allocated and thrown one at a time, when each level returns.

Should I use external global variables? Calling helper function to force buffer allocation after recursive call? What I actually catch here are tips on the cleanest, most C-idiomatic way to get this behavior.

Edit: one additional question. If the same accumulator is passed to each func call, is it really impossible to leave the accumulator pointer in a global variable, and not push it onto the stack with every call?

Answer 1

Since it is used only one call at a time, you can simply pass it and pass it to all calls through the operand:

 void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer) { func(datastructure->left, accumulator, buffer); func(datastructure->right, accumulator, buffer); { // do some stuff } return; } 

Answer 2

One option is to break the function into a non-recursive "public" function that sets the buffer and calls the private recursive function for which you want to pass the buffer:

 struct func_buffer { char buffer[1000]; }; static void func_private(TypeName *dataStructure, LL_Node **accumulator, struct func_buffer* buf) { func_private(datastructure->left, accumulator, buf); func_private(datastructure->right, accumulator, buf); // do some stuff with *buf return; } void func(TypeName *dataStructure, LL_Node **accumulator) { struct func_buffer buffer; func_private( dataStructure, accumulator, &buffer); return; } 

Thus, users of the function do not have to worry about how the memory used by the recursive part of the function is managed. That way, you could easily change it to use a global or dynamically allocated buffer, if it became obvious that such a change was necessary or would make sense.

Answer 3

You can pass a buffer reference or use a global variable.

When you use the link as in

 void func(TypeName *dataStructure, LL_Node **accumulator, char buffer[]) { func(datastructure->left, accumulator, buffer); func(datastructure->right, accumulator, buffer); { char buffer[1000]; // do some stuff } return; } void main() { char buffer[1000]; func (structure, accum, buffer); } 

you are passing a link, just a pointer to the beginning of the array, so you need to remember its length.

If you decide to use a global variable, you do not actually use the stack, but allocate program memory, a common space where code and data coexist (code is data). Therefore, you never use one byte of an extra bar in your calls if you do it this way:

 char buffer[1000]; void func(TypeName *dataStructure, LL_Node **accumulator) { func(datastructure->left, accumulator); func(datastructure->right, accumulator); { // do some stuff } return; } void main() { func (structure, accum); } 

It is up to you to choose one. The second is for each recursive call, but increases the size of the program. The first one is more elegant for some, but a little slower, perhaps not even noticeable.

Answer 4

I would personally allocate a buffer on the heap in this scenario like this:

 void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer ) { bool alloced = false; if( buffer == 0 ){ buffer = (char*) malloc( 1000 ); alloced = true; } func(datastructure->left, accumulator, buffer); func(datastructure->right, accumulator, buffer); { // do some stuff } if( alloced ) free( buffer ); return; } 

If you are not against C ++ syntax, you can have the default buffer equal to zero, or you can cripple the function name and add

 #define func(a,b) __mangledfunc__(a,b,0) 

It seems like this would be easiest for your application.

Answer 5

I believe that your average compiler can optimize the so-called "tail recursive functions", where basically the last instruction in your function is a recursive call to this function. In this special case, the function will simply reuse the stack frame with each recursion (so that all the variables you highlighted in the stacks will not be deleted / redistributed!) If you can click all your instructions before the recursive calls, and you have a decent compiler, it should work - otherwise, I would just pass it as a reference variable.