Returning recursive ternary freaks out

Question

Hi, assume this following function:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + max(findHeight(n->left), findHeight(n->right));
    }
}

Pretty standard recursive treeHeight function for a given binary search tree binaryTree. Now, I was helping a friend (he's taking an algorithms course), and I ran into some weird issue with this function that I couldn't 100% explain to him.

With max being defined as max(a,b) ((a)>(b)?(a):(b)) (which happens to be the max definition in windef.h), the recursive function freaks out (it runs something like n^n times where n is the tree height). This obviously makes checking the height of a tree with 3000 elements take very, very long.

However, if max is defined via templating, like std does it, everything is okay. So using std::max fixed his problem. I just want to know why.

Also, why does the countLeaves function work fine, using the same programmatic recursion?

int binaryTree::countLeaves(node *n) {
    if (n == NULL) {
        return 0;
    } else if (n->left == NULL && n->right == NULL) {
        return 1;
    } else {
        return countLeaves(n->left) + countLeaves(n->right);
    }
}

Is it because in returning the ternary function, the values a => countLeaves(n->left) and b => countLeaves(n->right) were recursively double called simply because they were the resultants?

Thank you!

The question was answered below

I just wanted to link some literature on the subject for future reference:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx

The main difference between the two implementations being:

#define max(i, j) (((i) > (j)) ? (i) : (j))

vs

template<class T> T max (T i, T j) { return ((i > j) ? i : j) }

Thank you all!

Answer 1

That max macro evaluates the arguments twice - and since your argument is a recursive function call, that's probably the source of the perf problem.

Answer 2

It's because of the definition of max. You're making 3 calls to findHeight() instead of 2.

Answer 3

Macros are expanded by the preprocessor, before the compiler gets to see the code. This means that, for example, macro parameters might be evaluated more than once.

With your macro, you're going to end up with something akin to:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        return 1 + (findHeight(n->left) > findHeight(n->right)) ? // call once...
                    findHeight(n->left) : findHeight(n->right); // and ouch
    }
}

As you can see, it's going to evaluate both functions, then one more an additional time. This is why macros can be evil.

You can disable the macro by defining NOMINMAX prior to including the Windows headers. Then use the function in <algorithm> instead.

If he must use the macro, he'll have to store the calculations in a variable:

int binaryTree::findHeight(node *n) {
    if (n == NULL) {
        return 0;
    } else {
        const int leftHeight = findHeight(n->left);
        const int rightHeight = findHeight(n->right);
        return 1 + max(leftHeight, rightHeight);
    }
}

---

With a function, each call will be evaluated prior to calling the function. That is, it's somewhat like the previous code block. It evaluates the function's arguments, gets the results, then passes those into the std::max function. There are no repeated evaluations.

Answer 4

a better option would be to declare a function with following signature:

int max(int, int)

This will prevent the recursive expansion of macro.