在递归函数中使用堆栈

I need to use an stack in a recursive function. Between function recursive calls the stack has to keep the contents and only modified by push or pop operations inside the function.

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

A way to do this it to define a global stack variable like this:

可以这样定义全局堆栈变量:

StackPtr stack = createStack();

Another way is to pass an stack to the function:

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

int recursiveFunction(int n, StackPtr stack);

Is there a way to do this but without global stack or passing an stack to the function? The idea is to encapsulate completely the function so the user just has to call it independently of the program specifications. It is like to define an static stack that conserve the stacks contents between recursive calls.

是否有一种方法可以做到这一点，但没有全局堆栈或将堆栈传递给函数?其思想是将整个函数封装起来，这样用户就必须独立于程序规范来调用它。这就像定义一个静态堆栈，在递归调用之间保存堆栈内容。

I tried:

我试着:

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

But the function reset the stack each call. I had to create the stack in the way shown because if I put:

但是函数会重置每次调用的堆栈。我必须按照显示的方式创建堆栈，因为如果我输入:

static StackPtr stack = createStrack();

An "not initialized constant" error is thrown.

抛出一个“未初始化的常量”错误。

Thanks.

谢谢。

2 个解决方案

#1

The usual solution is to use a helper function. The main function creates the stack (or whatever object is necessary), calls the helper (which is the actual recursive function) and then frees the stack before returning:

通常的解决方案是使用辅助函数。主函数创建堆栈(或任何需要的对象)，调用助手(实际的递归函数)，然后释放堆栈，然后返回:

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;
}

Using a local static variable should normally be avoided since it makes the function non-reentrant and thread-unsafe.

通常应该避免使用本地静态变量，因为它使函数不可重入和线程不安全。

#2

You can do this:

你可以这样做:

int recursiveFunction(int n){
  static StackPtr stack;

  if (stack == NULL)
    stack = createStack();

  ...
}

Upon startup, stackis initialized to NULL. The first time recursiveFunction is called, stack will be initialized. That's it.

在启动时，stackis初始化为NULL。第一次调用递归函数时，将初始化堆栈。就是这样。

But if thread safety is required, this solution won't work.

但是如果需要线程安全，这个解决方案将不起作用。

#1