CODEWITHSUNDEEP
c++recursion
lisolm
lisolm

Reputation: 35

Incrementing in a recursive function

While working through tree-processing problems, I'm confused about best way to approach storing the number of instances a certain pattern has been observed.

For example, say I want to return the number of times of number in a Binary Search Tree is divisible by 2. I would walk through the tree recursively, check each key if it was divisible by two, and increment a counter.

Right now, the only way I can think to store this counter is by reference. For example:

DivByTwo(node, counter) {
    DivByTwo(node.left, counter)
    DivByTwo(node.right, counter)

    if (node.key % 2 == 0) 
      counter ++
}

And after this is finished, the value of counter will be the number of keys divisible by 2. Is this a proper way to approach this problem? Is there a better way to capture this data without forcing the user to pass some variable by reference?

Upvotes: 0

Views: 2569

Answers (3)

Juan Leni
Juan Leni

Reputation: 7588

You could do it by returning the result:

int DivByTwo(Node *node) {
   if (node == null_ptr)
       return 0;

   return DivByTwo(node->left) + DivByTwo(node->right) + (node->key%2==0);
}

Upvotes: 0

Matt Jordan
Matt Jordan

Reputation: 2181

Here is a way to avoid passing a ref parameter, although it requires being able to return a value (you don't include any type info, so I took a best guess at your types):

int DivByTwo(NodeType node){
    int result = DivByTwo(node.left) + DivByTwo(node.right);
    if(node.key % 2 == 0)
        result += 1;
    return result;
}

Upvotes: 5

Dale Wilson
Dale Wilson

Reputation: 9434

Passing the counter by reference works and is a reasonable "small" solution. If you want a more formal, more complex, but more adaptable to future needs solution consider implementing the visitor pattern which is described in many places on the net including in Wikipedia

Upvotes: 0

Related Questions