在递归函数中使用堆栈

Question

我需要在递归函数中使用堆栈.在函数递归调用之间,堆栈必须保留内容,并且只能通过函数内的push或pop操作进行修改.

这样做的方法是定义一个像这样的全局堆栈变量:

StackPtr stack = createStack();

另一种方法是将堆栈传递给函数:

int recursiveFunction(int n, StackPtr stack);

有没有办法做到这一点但没有全局堆栈或将堆栈传递给函数？这个想法是完全封装功能,因此用户只需要独立于程序规范调用它.这就像定义一个静态堆栈,它保存递归调用之间的堆栈内容.

我试过了:

int recursiveFunction(int n){
    static StackPtr stack = NULL;
    stack = createStack();
...
}

但是该函数会在每次调用时重置堆栈.我必须以显示的方式创建堆栈,因为如果我放:

static StackPtr stack = createStrack();

抛出"未初始化的常量"错误.

谢谢.

Answer 1

通常的解决方案是使用辅助函数.main函数创建堆栈(或任何必要的对象),调用帮助器(这是实际的递归函数),然后在返回之前释放堆栈:

static int helper(StackPtr stack, int n) {
    ... /* Recursive calls to helper */
}

int mainFunction(int n){
    StackPtr stack = createStack();
    int rv = helper(stack, n)
    freeStack(stack);
    return rv;
}

通常应避免使用本地静态变量,因为它使函数不可重入且线程不安全.