Using an stack inside recursive function

Question

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.

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.

Answer 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.

Answer 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.

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