为递归函数添加返回大小写

Question

当涉及到递归时，这是我挣扎的地方，我知道函数何时应该为真的边缘情况，但是因为我必须添加一个返回false语句，并且在调用堆栈的深处，它确实变为真(这是检查的全部意义!)，我希望最终结果为真，并且递归停止。但最终，它会找到返回false的方法，因为这是函数做的最后一件事。

public boolean isPathHelper(Node node, String input){
    if(node.accept == true){
        return true;
    }else{
        if(input.length() == 0){
            return false;
        }
        isPathHelper(getNextState(node, input.charAt(0) -'0'), input.substring(1));
        return false;
    }

我该如何处理这种情况?我知道全局变量可以帮助，但我希望我的知识有差距，而不是。

Answer 1

试试这个:

public boolean isPathHelper(Node node, String input, int count){
    if(input.length() == 0){
        return false; //I can't go any further: return "failed"
    }
    else if(count == input.length()){
        return true; //if I ever reach here, then I am done: return "success"
    }
    // else call self recursively
    return isPathHelper(
      getNextState(node, input.charAt(0) -'0'), input.substring(1), count+1);
}

只要仔细检查你的逻辑和数据，以确保你在某个时候点击了"count == input.length()"。最好是在堆栈用完之前;)