如何在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]);
    }
}

由于我在循环中使用的局部变量,compile(gcc)为这个函数创建了一个大于I-like的堆栈帧(即使有很多pushq和popq指令-O3),这是一个问题,因为它是深刻的递归.由于我访问节点的顺序无关紧要,我可以重构此代码以使用一堆Node指针,从而减少每次迭代一个指针的开销.

1. 是否有任何提示我可以给编译器(gcc)解决这个问题？
2. 如果没有,是否可以将调用堆栈本身用于我的指针堆栈而无需求助于汇编？

Answer 1

您可以将计算放入自己的非递归函数中吗？这样，当您进行递归调用时，所有临时变量的堆栈将不存在。

更新：看起来局部变量中至少有一些数据对于递归是必不可少的。您可以使用alloca在堆栈上显式分配内存。