假设我有一些操纵图形结构的递归函数:
typedef struct Node {
Data data;
size_t visited;
size_t num_neighbors;
struct Node *neighbors[];
} Node;
void doSomethingWithNode(Node *node)
{
if ((!node) || node->visited)
return;
node->visited = 1;
/* Do something with node->data */
size_t /* some local variables */;
size_t i;
for (i = 0; i < node->num_neighbors; i++)
{
/* Do some calculations with the local variables */
if (/* something */)
doSomethingWithNode(node->neighbors[i]);
}
}
由于我在循环中使用的局部变量,编译器 (gcc
) 为此函数创建了一个比我想要的更大的堆栈帧(大量的 pushq
和 popq
指令甚至使用 -O3
),这是一个问题,因为它是深度递归的。由于访问节点的顺序无关紧要,我可以重构此代码以使用一堆 Node
指针,从而将每次迭代的开销减少到一个指针。
- 我可以给编译器 (
gcc
) 一些提示来解决这个问题吗? - 如果不是,是否可以在不借助汇编的情况下将调用堆栈本身用于我的指针堆栈?
最佳答案
您可以维护一个要访问的节点的 vector 或列表(或某个队列,或者可能是一个堆栈,甚至是一些任意的无序集)(并且您可能想要维护一个已访问节点的集合或哈希表) .
然后你将有一个循环,它选择要访问的容器前面的节点,并可能在该容器的后面添加一些未访问的节点....
阅读有关 continuation passing style 的维基页面关于tail calls
Google 还提供了 Deutsch Schorr Waite 算法,它可以给您一些想法。
关于c - 如何减少 C 中深度递归函数的堆栈帧?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28501480/