优化C中的递归调用
我有一个递归函数,可以这样写:
void func(TypeName *dataStructure, LL_Node **accumulator) {
func(datastructure->left, accumulator);
func(datastructure->right, accumulator);
{
char buffer[1000];
// do some stuff
}
return;
}
我知道,实际上缓冲区正在函数的开始处分配,并且将语句放在嵌套的作用域块中实际上并不使用新的堆栈帧。 但我不希望编译器一次分配一个指数数量的1000字节缓冲区,因为每个级别返回时,它们可以一次一个地分配和丢弃。
我应该使用外部全局变量吗? 调用助手函数强制在递归调用之后分配缓冲区? 我真正在这里捕捞的是关于强制这种行为的最干净,最C语言的方式的建议。
编辑:一个附加问题。 如果完全相同的accumulator
会传递给每次func
调用,那么是否听到将accumulator
指针留在全局变量中,而不是每次调用时都将其推入堆栈?
由于它一次只能被一个调用使用,因此您可以预先分配它并通过操作数将其传递给所有调用:
void func(TypeName *dataStructure, LL_Node **accumulator, char *buffer) {
func(datastructure->left, accumulator, buffer);
func(datastructure->right, accumulator, buffer);
{
// do some stuff
}
return;
}
一种选择是将函数分解为一个非递归的“公共”函数,该函数设置缓冲区并调用需要传入缓冲区的私有递归函数:
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;
}
这样,函数的用户就不需要关心函数的递归部分所使用的内存如何管理的细节。 所以你可以很容易地改变它使用一个全局的或动态分配的缓冲区,如果它变得明显,这种变化是必要的或将是有意义的。
您可以将参考传递给缓冲区或使用全局变量。
当你使用参考时
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);
}
你传递的是引用,只是指向数组开头的指针,所以你必须记住它的长度。
如果您选择使用全局变量,那么实际上不使用堆栈,而是分配程序存储器,即代码和数据共存(代码为数据)的共享空间。 因此,如果你这样做,你永远不会在你的调用中使用单个字节的额外ram:
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);
}
这取决于你选择一个。 第二个参数在每次递归调用时将较少的参数压入堆栈,但会扩大程序大小。 第一个对一些更优雅,但速度稍慢,可能不明显。
链接地址: http://www.djcxy.com/p/84319.html