2

我来自 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;
}

我非常了解前者相对于后者的优势；后者比前者有什么优势？它与堆栈内存使用有关，对吧？

4

2 回答 2

1

我认为第二种解决方案与第一种解决方案相比没有任何优势。事实上，我认为第一个更糟糕。第一个更简洁，检查空指针的代码行更少。

但是，您的问题的标题具有误导性。第二个也是递归的。它不是迭代的。

于 2016-03-09T05:14:51.153 回答
1

后一种方式在 C++ 风格中做得不好的一件事是，为了通过引用调用的效果，它仍然传递指针，在 C++ 中我们确实有引用，这使得代码更清晰，更不容易出错：

void MovieTree::countMovieNodes(MovieNode* parent, int& count)
{
  ++count;
  ....
}

回到递归的风格，后一种情况使用的风格，由于尾调用优化，可以有更好的性能。

简而言之，TCO 避免了调用堆栈随着递归调用的每一级而不断增加。

在前一种形式中，我们需要为每个级别的递归调用保留堆栈，以便我们可以获得结果并进行进一步计算（在您的情况下，计算两个子树中的计数总和）。

对于后一种情况，编译器知道它不需要为第二次调用保留堆栈countMovieNodes（因为没有进一步的计算），以便它可以重用当前堆栈来执行递归调用（如果我的理解是正确的）。

但是，在这种特定情况下，收益可能不会那么大，因为对于后一种情况，第一次调用countMovieNodes无法从 TCO 中受益。尽管如此，它仍然是一个优势。

于 2016-03-09T06:35:52.573 回答