java - 这些 BST 算法中哪个更实用？

Question

我这里有两种算法可以反射(reflect) BST。它们都工作正常，但据我所知，第二个是递归的，第一个是尾递归的。我知道在 Java 中，编译器不会针对尾递归进行优化，但我的问题是——在任何其他语言中，这两种算法中哪种算法更好？这是一个太主观的问题吗？

public Node mirror(Node root, Node newRoot) {
    newRoot.item = root.item;
    if (root.right != null) {
        newRoot.left = new Node();
        newRoot.left.item = root.right.item;
        mirror(root.right, newRoot.left);
    }
    if (root.left != null) {
        newRoot.right = new Node();
        newRoot.right.item = root.left.item;
        mirror(root.left, newRoot.right);
    }
    return newRoot;
}

///VERSION 2////

public Node mirror(Node currentNode) {
    if (currentNode == null) {
        return null;
    } else {
        Node newnode = new Node();
        newnode.item = currentNode.item;
        newnode.left = mirror(currentNode.right);
        newnode.right = mirror(currentNode.left);
        return newnode;
    }
}

Answer 1

一些事情:

首先，许多命令式语言并未针对尾递归进行优化。这对于函数式语言来说是很常见的，如果你想要这个特性，你应该使用其中的一种。 Scala 可能是一个不错的选择，因为它使用了 JVM。此外，对于 Scala，您需要专门注释要使尾递归的内容

第二，第二段代码不是尾递归的。尾递归是一个相当强的要求:如果代码以连续传递方式解释，则递归调用必须是最后执行的事情。实际上，这意味着您的 return 语句必须是唯一执行递归的语句。例如，在类似 C 的伪代码中:

int factorial(int x) {
  if (x == 0) return 1;
  else return x*factorial(x-1);
}

这不是尾递归，因为乘法需要在递归调用之后但在 return 语句之前完成。这是一个尾递归版本:

int factorial_helper(int acc, int x) {
   if (x == 0) return acc;
   else return factorial_helper(acc*x, x-1);
}

int factorial(int x) { return factorial_helper(1, x); }

您可以在 factorial_helper 中看到递归调用返回的值正是函数返回的值——这就是使这个尾部递归的原因。

在你的第二个算法中，有两个递归调用。在每次递归调用中，镜像树的地址都存储在新节点中。然后返回newnode的地址(Java暗地里有指针)。因此，这不是尾递归编写的，因为您没有返回递归调用的确切结果。

第三:对于这样的事情，查看哪个性能更好的最佳方法是同时运行和基准测试:)。我没有看到任何明显的算法单独的赢家(也许其他人看到了？)。看起来不会有任何渐近差异，尽管将其重写为实际尾递归可能会加快速度。