0

I'm having some trouble deciphering where my coding is going astray here. In order to implement the size function of dictionary.c I have written a side function called counter to take care of the actual counting. I did this because it seemed like a recursive function might do the job nicely. Unfortunately, this is my first foray into recursive functions and it's giving me a bit of a headache.

I've used small dictionary which should count 2 words (and load does indeed mark only 2 words). However, when the program is run with the function as below, it counts 18. Using gdb, I've determined that it is counting the end of the first word (cat), then proceeds to count the second word (caterpillar) 8 times, it then runs until it goes back to the end of the first word and counts it once more, then back to the end of the second word 8 more times (1 + 8 + 1 + 8 if that was confusing). I just can't figure out why it is doing this.

Code for the counter function is:

void counter (node* leaf)
{
    // check to see if is a word
    if (leaf->is_word == true)
    {
        *count +=  1;
    }

    for (int i = 0; i < 27; i++)
    {

        //look for pointer to the next leaf
        if (leaf->children[i] != NULL)
        {
                leaf = leaf->children[i];
                counter(leaf);
        }

    }

    return;
}

count is simply a int pointer (that may change later) and does indeed start at 0 and the is_word member of all other nodes is false. I just don't know why it's counting multiple times. I feel like if I could understand why 8 time and why twice it would be so much easier to find a way to fix it.

1

The problem lies in this block of code:

    if (leaf->children[i] != NULL)
    {
            leaf = leaf->children[i];
            counter(leaf);
    }

Here's why it's going everywhere. You want it to go to the first node of the root, traverse down and then come back to do the second node of the root. Because of the leaf = leaf->children[i]; statement, it goes to root->children[1], goes down and comes back up, but then goes to root->children[1]->children[2]. With each pass through the loop, it cycles one level further down and to the right instead of straight across.

If you want to see where it's going, add a couple extra global variable counters and printf statements to the code. (I wasn't feeling motivated to exactly track the path it follows.) Put separate counters in each printf so you know how often each gets hit and you can start to see what's going on.

Easy fix. Remove the reassignment.

if (leaf->children[i] != NULL)
{
        counter(leaf->children[i]);
}

This keeps any given recursion looping through all 27 children of the same node instead of climbing down and up through the trie when it shouldn't.

If this answers your question, please accept the answer to remove your question from the unanswered question pool. Let's keep up on forum maintenance. ;-)

1
  • That was it exactly! Thanks, the recursive part kept confusing me a bit. I'm going to have to keep looking through that to make sure I follow it.
    – reddisht
    Jul 10 '15 at 23:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .