java - 如何停止递归

Question

这是我的 find() 方法:

public boolean find(int key) {

    BinTreeNode node = findHelper(key, root);
    if (node == null) {
        return false;
    } else {
        return true;
    }
}    


private BinTreeNode findHelper(int key, BinTreeNode node) {
    if (node == null) {
        return null;
    }    
    if(key == node.item) {
        return node;
    }
    else if(key < node.item) {
        return findHelper(key,node.leftChild);
    }
    else {
        return findHelper(key,node.rightChild);
    }
}

这是我修改后的代码。还是不行:(

public boolean searchNum(BinTreeNode node, int num) {
    if(node == null) {
        return false;
    }
    else {

        int result = num - node.item;
        if(find(result)) {
            return true; 
        }

        if(node.leftChild != null) {
            searchNum(node.leftChild, num);
        }

       if(node.rightChild != null) {
            searchNum(node.rightChild, num);
        } 

       return false;
    }
}

我试图找出给定的数字是否等于二叉搜索树中任意两个数字的总和。我知道错误在哪里，但不知道如何纠正。

下面几行

if(find(result)) {

return true; 

}

应该终止该方法，因为一旦我得到 true，这就是我所需要的，我应该将值返回给调用函数。但是，递归继续执行，最终返回上次递归调用的值。请帮忙。

public boolean searchNum(BinTreeNode node, int num) {
    if(node == null) {
        return false;
    }
    else {
        if(node.leftChild != null) {
            searchNum(node.leftChild, num);
        }
        int result = num - node.item;
        System.out.println(node.item);
        //I have a separate find() which finds if the key is in the tree
        if(find(result)) {
            return true; 
        }

       if(node.rightChild != null) {
            searchNum(node.rightChild, num);
        } 

       return false;
    }
}
}

Answer 1

最通用的递归公式如下:

function sampleRecursion(a){
    if(isTerminalCase) {
        return true;
    }
    else {
       a = modify(a);
       return sampleRecursion(a);
    }
}

使用它作为代码模板，您应该拥有如下内容:

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input
    if(node == null) {
        return false;
    }
    //this is your terminal case
    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if(find(result)) {
        return true; 
    }
    //this if doesn't make any sense as you validate this input already
    //if(node.leftChild != null) {
    //    searchNum(node.leftChild, num);
    //}
    //here is where we are returning the value we get back from searchNum
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);
    //System.out.println(node.item);
    //I moved this up into the single return case, so everything after this is unnecessary
    //if(node.rightChild != null) {
    //    searchNum(node.rightChild, num);
    //} 
    //return false;
}

所以，清理后，应该看起来像:

public boolean searchNum(BinTreeNode node, int num) {
    //validate the input
    if(node == null) {
        return false;
    }
    //this is your terminal case
    int result = num - node.item;
    //I have a separate find() which finds if the key is in the tree
    if(find(result)) {
        return true; 
    }
    //here is where we are returning the value we get back from searchNum
    return seachNum(node.leftChild, num) || searchNum(node.rightChilde, num);
}

这是递归函数的近似值。我不知道 find 函数是做什么的，所以我不知道它是否会达到你想要的效果。

此外，根据您的描述，您试图在搜索树中使用两个数字，而不是一个。在您现在拥有的代码中，您只使用了一个。所以如果你传入，比如说，({a node}, 15)，你会得到......一些东西。如果你的 find 函数调用 searchNum({top node}, result)，我想你会没事的。但我不知道 find 的作用，所以我不能肯定地说。

编辑:合并 find 和 findHelper 可能会更简单。

private boolean find(int key, BinTreeNode node) {
    if (node == null) {
        return false;
    }    
    if(key == node.item) {
        return true;
    }
    else if(key < node.item) {
        return findHelper(key,node.leftChild);
    }
    else {
        return findHelper(key,node.rightChild);
    }
}

然后只需在 searchNum 中使用 find(result, root) 调用它即可。也就是说，如果您有权访问 searchNum 中的 root。