Обход изменяемого и неизменяемого двоичного дерева в переполнении стека
Я родом из Python и Haskell, поэтому, когда мне пришлось написать функцию для подсчета количества фильмов в двоичном дереве, я сделал это так:
int MovieTree::countMovieNodes(MovieNode* parent)
{
if (parent)
return countMovieNodes(parent->left) + countMovieNodes(parent->right) + 1;
else
return 0;
}
int MovieTree::countMovieNodes()
{ countMovieNodes(root); }
Однако, используя файл заголовка, предоставленный в классе, я должен был сделать это так:
void MovieTree::countMovieNodes(MovieNode* parent, int* c)
{
(*c)++;
if (parent->left)
countMovieNodes(parent->left, c);
if (parent->right)
countMovieNodes(parent->right, c);
}
int MovieTree::countMovieNodes()
{
if (!root) return 0;
int c=0; countMovieNodes(root, &c); return c;
}
Я хорошо понимаю преимущества первого перед вторым; Каковы преимущества последнего перед первым? Это связано с использованием стековой памяти, верно?
Решение
Я не вижу никакого преимущества во втором решении по сравнению с первым решением. На самом деле, я думаю, что хуже первого. Первый — чище, с меньшим количеством строк кода, которые проверяют нулевые указатели.
Однако название вашего вопроса вводит в заблуждение. Второй тоже рекурсивный. Это не итеративно.
Другие решения
Последнее, что плохо работает в стиле C ++, это то, что он все еще передает указатель ради эффекта вызова по ссылке, для которого в C ++ есть ссылка, которая делает код чище и менее подвержен ошибкам:
void MovieTree::countMovieNodes(MovieNode* parent, int& count)
{
++count;
....
}
Возвращаясь к стилю рекурсии, стилю, который используется в последнем случае, может иметь лучшую производительность из-за оптимизации хвостового вызова.
Короче говоря, TCO избегает стека вызовов продолжает увеличиваться для каждого уровня рекурсивного вызова.
В предыдущей форме нам нужно хранить стек для каждого уровня рекурсивного вызова, чтобы мы могли получить результаты и выполнить дальнейшие вычисления (в вашем случае вычисление суммы счета в двух поддеревьях).
В последнем случае компилятор знает, что ему не нужно хранить стек для второго вызова countMovieNodes (потому что дальнейших вычислений нет), чтобы он мог повторно использовать текущий стек для выполнения рекурсивного вызова (только для второго вызова, если мое понимание верно).
Однако в этом конкретном случае выгода может быть не такой большой, потому что для последнего случая первый вызов countMovieNodes не может извлечь выгоду из TCO. Это все еще преимущество, хотя.