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.

May be static local? I would pass the stack structure pointer as an argument. Also, what is 'StackPtr' is it a class? — phoxis
– phoxis, Commented Apr 23, 2018 at 15:19
You can add a boolean variable initialized with initial value of false to your try with the static stack. If it is false (will be so on the first call), create the stack and mark it true. — s7amuser
– s7amuser, Commented Apr 23, 2018 at 15:23
Not directly related, but I'd rethink the design. If you use an explicit stack, why do you need recursion in the first place? :o — user2371524
– user2371524, Commented Apr 23, 2018 at 15:29
Possible duplicate of How to initialize static pointer with malloc in C? — Christian Gibbons
– Christian Gibbons, Commented Apr 23, 2018 at 15:32
But each return addres, recursive or not, each local stack frame, recursive or not, each saved group of machine registers are stored/pushed an then back popped from the system global stack setup by the program loader and/or startup code before main() is called. — ulix
– ulix, Commented Apr 23, 2018 at 15:43

rici · Accepted Answer · 2018-04-23 15:29:39Z

8

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.

answered Apr 23, 2018 at 15:29

rici

243k30 gold badges263 silver badges364 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Jabberwocky Over a year ago

If the createStack and freeStack functions are expensive, this may not be the best solution. I upvoted this answer anyway.

carlitos_30 Over a year ago

I wanted to avoid calling the function with an stack parameter.

rici Over a year ago

@carlitos_30: you call the main function, so the caller doesn't need to know anything about stacks. The rest is an implementation detail.

rici Over a year ago

@michael: if the stack functions are expensive, they themselves could recycle stacks using a mutex-protected pool. However, it is very rare for that to be worthwhile.

carlitos_30 Over a year ago

@rici I understood what you meant. I confused the "mainFunction", with the "main" function. Thanks.

Jabberwocky · Accepted Answer · 2018-04-23 15:51:35Z

4

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.

edited Apr 23, 2018 at 15:51

answered Apr 23, 2018 at 15:26

Jabberwocky

51.3k18 gold badges71 silver badges127 bronze badges

Collectives™ on Stack Overflow

Using an stack inside recursive function

2 Answers 2

5 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related