在递归方法中返回错误的计数

Question

尝试递归搜索时，我没有返回正确的数字。我正在使用它遍历使用单向链表实现的队列并返回该项目所在的索引，以便我可以确定我需要取消排队（）多少次才能到达该项目。

public int search(E item) {
    return recSearch(item, head);
}
public int recSearch(E item, Node node){
    if (head == null){
        return -1;
    }else if (node.data.equals(item)){
        return searchCnt;
    }else{
        searchCnt++;
        return recSearch(item, node.next);
    }
}

我觉得它应该正确计数，因为每次它未能满足 if 和 else if 条件时都必须计数，但我没有在正确的位置增加吗？还是我完全偏离了？感谢您的帮助！

Answer 1

您需要在

调用recSearch()之前在search()内部将searchCnt设置为 0。另外，您需要测试是否node == null，而不是head == null。

或者，您可以尝试以下方法：

public int search(E item) {
    return recSearch(item, head, 0);
}
public int recSearch(E item, Node node, int index){
    if (node == null){
        return -1;
    }else if (node.data.equals(item)){
        return index;
    }else{
        return recSearch(item, node.next, index + 1);
    }
}

它消除了对类/实例变量的需求。

请注意，这不允许在节点上null数据。要支持null值，您需要在检查node == null后立即使用另一个if/else分支：

}else if (item == null && node.data == null) {
    return index;
}

Answer 2

您需要在

递归时传递 searchCnt var，以便正确更新它。

public int search(E item) {
    return recSearch(item, head, 1);
}
public int recSearch(E item, Node node, int searchCnt){
    if (head == null){
        return -1;
    }else if (node.data.equals(item)){
        return searchCnt;
    }else{
        return recSearch(item, node.next, ++searchCnt);
    }
}

初始调用中的1假定，如果您在 recSearch 的第一次迭代中找到您的项目，则计为一次搜索（在这种情况下，search将返回1）。