pset4 speller using trie. Problem with the size function

Question

i was working on pset4 speller using trie. i wanted to use recursion to find the size of the dictionary loaded. But nothing is working. According to what debugger is doing, i think that it is probably not returning to what sizer was pointing previously. For example in a dictionary of :

a
aa
aab
ab

the size is able to read the first three. but when i am returning the counter to the previous size, it does not read the letter b after a. I think it is still checking the array in which it is reading aab. what can i do ???

unsigned int size(void)
{
    int ctr = 0;
    for (int i = 0; i < N; i++)
    {
            if (sizer -> children[i] == NULL)
            {
                continue;

            }
            else
            {
                // do i need to use a pointer here to point 
                                // to sizer before changing it

                sizer = sizer -> children[i];
                if ((sizer -> is_word) == true)
                {
                    ctr ++;
                }

                int x = size();
                ctr += x;

            }

    }
    // Before returning ctr should i use the pointer to change sizer to     
    // what it was previously . Can it work???

    return ctr;
}

Answer 1

I think it is still checking the array in which it is reading aab. what can i do ???

I think you're right.

Consider how you update the value of global variable sizer in this code. The only way you ever do that is this:

sizer = sizer -> children[i];

Since you only ever set sizer to point to one of the children of the current node, never restoring it to a previous value, the program follows exactly one path from the root to a leaf, and then it's exhausted its capabilities. With different inputs you can demonstrate for yourself that this is what is happening. For example,

a
b
ba

will report a count of 1, since it traverses node "a" first, and it's a leaf.

Global variables can very easily get you into trouble, especially modifiable ones. Start now cultivating a habit of avoiding their use. Prefer to convey information to functions via arguments, instead.

Also prefer to avoid recursion under most circumstances, and don't even consider combining recursion with modifiable global variables until you have a lot more experience (which at that point will tell you "I want no part of that").

It's unclear what is the type of sizer, but suppose it is struct sizer *. In that case, consider what other changes would be needed to change the function signature to

unsigned int size(const struct sizer *node_sizer);

That's not just a style thing. Done properly, it will resolve your functional issue, too.