Возвращение рекурсивных троичных уродов

Question

примите следующую функцию:

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

Довольно стандартная рекурсивная treeHeight функция для заданного бинарного дерева поиска binaryTree. Теперь, я помогал другу (он проходит курс алгоритмов), и я столкнулся с какой-то странной проблемой с этой функцией, которую я не мог на 100% объяснить ему.

Когда max определено как max(a,b) ((a)>(b)?(a):(b)) (что является максимальным определением в windef.h), рекурсивная функция выходит из строя (она запускается примерно в n^n раз, где n - высота дерева). Это, очевидно, делает проверку высоты дерева с 3000 элементами очень и очень долгой.

Однако, если max определяется с помощью шаблонов, как это делает std, все в порядке. Так что использование std::max решило его проблему. Я просто хочу знать, почему.

Кроме того, почему функция countLeaves работает нормально, используя ту же программную рекурсию?

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);
    }
}

Это потому, что при возврате троичной функции значения a => countLeaves(n->left) и b => countLeaves(n->right) были рекурсивно дважды вызваны просто потому, что они были результатом?

Спасибо!

На вопрос был дан ответ ниже

Я просто хотел связать некоторую литературу по этому вопросу для дальнейшего использования:
http://www.boostpro.com/tmpbook/preprocessor.html
http://msdn.microsoft.com/en-us/library/z3f89ch8.aspx

Основное различие между двумя реализациями:

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

против

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

Спасибо всем!

Answer 1

Макросы расширяются препроцессором до того, как компилятор увидит код. Это означает, что, например, макропараметры могут оцениваться более одного раза.

С вашим макросом вы получите нечто похожее на:

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
    }
}

Как вы можете видеть, он собирается оценить обе функции, а затем еще одну дополнительную. Вот почему макросы могут быть злыми.

Вы можете отключить макрос, определив NOMINMAX перед включением заголовков Windows. Затем используйте функцию в <algorithm>.

Если он должен использовать макрос, ему придется хранить вычисления в переменной:

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);
    }
}

---

С функцией каждый вызов будет оцениваться до до вызова функции. То есть это похоже на предыдущий блок кода. Он оценивает аргументы функции, получает результаты, а затем передает их в функцию std::max. Нет повторных оценок.

Answer 2

Этот макрос max оценивает аргументы дважды - и поскольку ваш аргумент является рекурсивным вызовом функции, это, вероятно, источник проблемы perf.

Answer 3

лучшим вариантом было бы объявить функцию со следующей подписью:

int max(int, int)

Это предотвратит рекурсивное расширение макроса.

Answer 4

Это из-за определения макс. Вы делаете 3 звонка findHeight () вместо 2.