Memory-optimizing recursive calls in C

I have a recursive function which can be written like:

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 reality the buffer is being allocated at the beginning of the function and putting the statement in a nested scope block doesn't actually use a new stack frame. But I don't want the compiler to allocate an exponential number of 1000-byte buffers at once, when they can be allocated and thrown away one at a time as each level returns.

Should I use outside global variables? A call to a helper function to force the buffer to be allocated after the recursive call? What I'm really fishing for here is advice on the cleanest, most C-idiomatic way of forcing this behavior.

Edit: One add-on question. If the exact same accumulator will be passed to every call of func, is it unheard of to leave the accumulator pointer in a global variable rather than pushing it onto the stack with every call?

Since it's only used by one call at a time, you can just preallocate it and pass it into all the calls via an operand:

void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer) {
    func(datastructure->left, accumulator, buffer);
    func(datastructure->right, accumulator, buffer);

    {
        // do some stuff
    }

    return;
}  

One option is to break the function into a non-recursive "public" function that sets up the buffer and calls a private recursive function that requires a buffer be passed in:

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

That way the users of the function don't need to be concerned with the details of how the memory used by the recursive part of the function is managed. So you could pretty easily change it to use a global or a dynamically allocated buffer if it became evident that such a change was necessary or would make sense.

You can either pass the reference to the buffer or use global variable.

When you use the reference 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 the reference, just the pointer to the beginning of the the array, so you have to remember its length.

If you choose to use a global variable, you are actually not using stack, but allocating program memory, a shared space where code and data coexists (code is data). Therefore, you are never using a single byte of extra ram in your calls if you do it like this:

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 one pushes less parameters onto the stack on each recursive call, but enlarges the program size. The first one is more elegant to some, but is a bit slower, maybe not even noticeable.

I would personally allocate the buffer on the heap in this scenario somewhat 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 don't mind C++ syntax, you could have buffer default to equal zero, or you could mangle the function name and add

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

That seems like it would be the easiest for your application.

I believe your average compiler can optimize what are known as "tail recursive functions", where basically the last instruction in your function is a recursive call to that function. In that special case, the function will simply reuse the stack frame with every recursion (so all of your stack allocated variables don't get un/re-allocated!) If you can push all of your instructions before the recursive calls, and you have a decent compiler, it should work-- otherwise, I'd just pass it around as a reference variable.