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?

---

由于它一次只能被一个调用使用，因此您可以预先分配它并通过操作数将其传递给所有调用：

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.

链接地址: http://www.djcxy.com/p/84320.html

上一篇: C ++如何自动调用析构函数？

下一篇: 优化C中的递归调用