Recursive function does not work without saving parameter

Question

I have a recursive function which runs through a quadtree and generates for each node a key. But this only works when I save the variable myKey as myKey1. If I do not do that, the resulting keys are wrong. But why? That is not clear to me.

Here is the function:

void keygen(tree *tn, long unsigned int myKey)
{
    long unsigned int myKey1 = myKey; // Why do I need this line?

    for(int q=0; q<4; q++){
        // 1) Check if child exists
        if(tn->child[q] != NULL){
            // Make key
            myKey1 = (myKey<<DIM)|q;
            // Save key
            tn->child[q]->key = myKey1;
            // Call again if leaf               
            if(tn -> child[q] -> isLeaf == 0){ 
                keygen(tn->child[q], myKey1);
            }
        }
    }   
}

Because of the line myKey1 = (myKey<<DIM)|q;? If you were originally using myKey on the left and right, you'd be accumulating shifts on every iteration of the loop. — happydave
– happydave, Commented Dec 5, 2016 at 17:53
@happydave Yes, now I see it. You are totally right! Thank you! — Gilfoyle
– Gilfoyle, Commented Dec 5, 2016 at 18:08
@alk: Mostly because I didn't have time to read the code carefully enough to be confident that this was the real issue. I guess I'll turn it into an answer now — happydave
– happydave, Commented Dec 5, 2016 at 21:06

happydave · Accepted Answer · 2016-12-05 21:11:16Z

2

This line is likely the issue

myKey1 = (myKey<<DIM)|q;

If you don't make a separate myKey1 variable, then you'll be shifting by DIM on every iteration of the loop, so by the fourth iteration, you'll have shifted by 4*DIM (and bitwise-ORed with various values of q between shifts).

It seems like your intent is to just shift and or once relative to the original key, which is what you accomplish by creating a new variable rather than modifying the original myKey in place.

answered Dec 5, 2016 at 21:11

happydave

7,2371 gold badge29 silver badges25 bronze badges

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

Collectives™ on Stack Overflow

Recursive function does not work without saving parameter

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related