无法理解当一个return语句必须用于有关的递归

Question

我是递归的概念刷牙并用二叉树的工作。我不明白，使用与递归调用等次return语句不使用时返回的实例之间的差别。我给的代码说明我的问题。

下面是检查某值存在于BST的函数：

public boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }

    if (value == current.data) {
        return true;
    }

    //HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
    return value < current.data
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
   }
}

下面是数据转换为BST的插入的函数：

public Node insert(Node current, int data) {
    if (current == null) {
        return createNode(data);
    } else if (data < current.data) {
        //RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
        current.left = insert(current.left, data);
    } else if (data > current.data) {
        current.right = insert(current.right, data);
    }

    return current;
}

我想我的问题归结为：“我们什么时候返回一个递归调用，我们什么时候呢？”

Answer 1

有两种类型的功能呈现，所以有我们需要遵循两个单独的规则。

以您所提供的第一功能：

public boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    }

    if (value == current.data) {
        return true;
    }

    //HERE, THE RECURSIVE CALL IS PRECEDED BY A RETURN STATEMENT
    return value < current.data
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
   }
}

该功能的目的是找到一个目标值，并将其返回。在这种情况下，我们返回一个递归调用时，我们要返回我们知道正在测试将通过节点的一个孩子提供一个值。

然而，取插入例如：

public Node insert(Node current, int data) {
    if (current == null) {
        return createNode(data);
    } else if (data < current.data) {
        //RECURSIVE CALL HERE WITHOUT USE OF A RETURN STATEMENT
        current.left = insert(current.left, data);
    } else if (data > current.data) {
        current.right = insert(current.right, data);
    }

    return current;
}

此代码是为了完成不同类型的任务。而不是寻求一个单一的目标值，该递归函数的目的是修改现有的树。在这种情况下，我们只返回我们要对现有的树（或重复的值）的修改。

Answer 2

由于Java没有做尾递归优化，你永远不会有“重返递归调用”。请参阅“Why doesn't Java have optimization for tail-recursion at all?”

请参阅“What is tail recursion?”如果你想了解如何在函数式语言的作品，但它并不适用于Java的。

在Java中，你做的递归调用的地方的方法，它会更有意义给你。你不必做它作为return语句的一部分。

Answer 3

递归之前的return关键字不是不同于这样的：

boolean res = value < current.data
    ? containsNodeRecursive(current.left, value)
    : containsNodeRecursive(current.right, value);

return res;

无论哪种方式递归完全评估之前，在当前函数调用可以返回。

“我们什么时候返回一个递归调用，当我们不应该？” - 你不是返回一个递归调用，您传回递归的结果，e.g一个boolean。您可以立即返回一个函数调用的结果，如果你没有任何更多的处理做。这显然需要函数调用返回作为当前功能预计将返还相同种类，这是递归保证，因为所谓的“自己”。

对于你的第一个代码片段，考虑功能做什么。它搜索的值，如果进一步发现树倒，那么布尔值仅仅是转发回了树。

在第二个例子中，树被改变为递归的一部分。对于任何节点current，递归返回左/右子树，那么它必须能够返回之前覆盖现有的左/右子树。