c - 如何减少 C 中深度递归函数的堆栈帧？

Question

假设我有一些操纵图形结构的递归函数:

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 指针，从而将每次迭代的开销减少到一个指针。

1. 我可以给编译器 (gcc) 一些提示来解决这个问题吗？
2. 如果不是，是否可以在不借助汇编的情况下将调用堆栈本身用于我的指针堆栈？

Answer 1

您可以维护一个要访问的节点的 vector 或列表(或某个队列，或者可能是一个堆栈，甚至是一些任意的无序集)(并且您可能想要维护一个已访问节点的集合或哈希表) .

然后你将有一个循环，它选择要访问的容器前面的节点，并可能在该容器的后面添加一些未访问的节点....

阅读有关 continuation passing style 的维基页面关于tail calls

Google 还提供了 Deutsch Schorr Waite 算法，它可以给您一些想法。