CODEWITHSUNDEEP
c++recursiondata-structuresstack
Ashwini
Ashwini

Reputation: 91

Behaviour of static variables in recursion

I am talking with reference to C++. I know that if an int is declared as static in recursion, its value is not reinitialized in stack-recursion call and the present value is used.

But if a stack becomes empty(or a recursion computation is complete) and then the recursion is called again, will it use the same static value as initialized in first stack call??

I will explain my problem in detail.

I am trying to code level order traversal in spiral form.

         1
       /   \
      2     3
     / \   / \
    7  6  5  4

Level order traversal in spiral form will give output 1 2 3 4 5 6 7.

void LevelSpiral(node* root, int level)
{
    static int k = level%2;
    if(root==NULL)
        return;
    if(level==1)
    {
        printf("%d ",root->val);
    }
    else
    {
        if(k==0)
        {
            LevelSpiral(root->left,level-1);
            LevelSpiral(root->right,level-1);
        }
        else
        {
            LevelSpiral(root->right,level-1);
            LevelSpiral(root->left,level-1);
        }
    }
}

void LevelOrderSpiral(node* root)
{
    for(int i=1;i<=maxheight;i++)
        LevelSpiral(root,i);
}

LevelOrderSpiral function makes separate LevelSpiral-call for each i. But throughout the code it always uses k=1(which is initialized in the first LevelSpiral-call with i=1) and prints the output as 1 3 2 4 5 6 7.

Shouldn't it print 1 2 3 4 5 6 7 as the function stack is reinitialized for every i?

Upvotes: 1

Views: 720

Answers (2)

Konrad Rudolph
Konrad Rudolph

Reputation: 545588

I know that if an int is declared as const in recursion, its value is not reinitialized in stack-recursion call and the present value is used.

No, that’s wrong. const has got nothing to do with recursion or reentrancy.

But if a stack becomes empty(or a recursion computation is complete) and then the recursion is called again, will it use the same const value as initialized in first stack call??

A const is a normal (albeit unmodifiable) variable: it is reinitialised whenever the initialisation statement is executed, i.e. on every function call. This is the same for any non-static variable.

static local variables exhibit the behaviour you are describing: they are only executed once, at the first call of that function, and, importantly, they are not reinitialised even after the call stack is “emptied”. It makes no difference whether the function is called repeatedly from outside, or recursively.

Upvotes: 1

John
John

Reputation: 7339

You need a static variable for it's value to be retained between calls, or from one call to the next recursive call.

Furthermore, recursion wouldn't be the first tool I reach for a breadth-first traversal. I would use a queue of node (safe) pointers (or reference wrappers or whatever). Put the root node in the queue, then loop until the queue is empty removing the front element and enqueueing all of it's child nodes and do what you want with the recently removed element.

Regarding your implementation, you are alternating between going to the left first and going to the right first. level always equals 1 at the row before the one you want to print, so you always traverse your printing row from right to left. You'll see bigger shufflings of the nodes when you have a deeper tree. Draw a sample tree on paper and draw the navigations on it as you follow your code by hand.

Upvotes: 2

Related Questions