java - LinkedLIst indexOf递归实现

Question

我很难理解在执行 indexOf() 后递归是如何进行的的 LinkedList作品:

/**
 * Returns the position of the first occurrence of the 
 * given character in this list, or -1 if there is no 
 * such occurrence.
 */
public int indexOf(char c)
{
    if (this.head == null)
    {
        return -1;
    }
    else
    {
        return LinkedList.indexOf(c, this.head);
    }
}
private static int indexOf(char c, Node node)
{
    if (node.data == c)
    {
        return 0;
    }
    if (node.next == null)
    {
        return -1;
    }
    int index = LinkedList.indexOf(c, node.next);
    if (index == -1)
    {
        return -1;
    }
    else
    {
        return 1 + index;
    }
}

哪里head是列表中的初始节点(“链接”)。

static indexOf()方法检查头部是否有数据匹配，然后是否存在下一个节点。假设两个条件都是 false (没有数据匹配并且存在下一个节点)。那么indexOf()在下一个(第二个)节点上递归调用以执行相同的检查。但是，如果两个条件仍然是false , 它返回到 int index 是什么鉴于没有 else index 之前的子句宣布？这似乎不合法。

当我在调试器中单步执行它时，它并没有返回任何东西，实际上它似乎做了更多的递归调用，直到 if 之一。满足条件(存在数据匹配或已到达列表末尾)。但它为什么要这样做呢？然后1怎么样？被添加到 index每次？

Answer 1

However, if both conditions are still false, what does it return to int index given that there's no else clause before index is declared?

它还不会返回任何东西，它会进入另一层递归:

indexOf(node) -> indexOf(node.next) -> indexOf(node.next.next) -> ...

然后，当满足条件时，它最终返回一个值，您开始从之前进行的每个递归调用中返回:

indexOf(node) <- indexOf(node.next) <- indexOf(node.next.next) <- ...

但这样做还会将返回的索引加 1，因此基本上计算您达到的递归级别等于您达到的节点编号，这是您正在寻找的索引。

此图显示了当第四个节点上存在匹配项时算法的工作原理。蓝色表示我们正在进入递归，红色表示我们正在递归回来(点击图片可以原图打开):

另一个图表显示了在第三个节点上匹配的情况下指令的执行顺序(单击图像以其原始大小打开它):