为什么这个printKthToLast递归(java)从头到尾开始

发布于08月29日

我正在研究算法，并在一段时间内仍在解决这一疑虑. 我理解递归背后的概念，但我不明白的是为什么下面的代码从链表的末尾开始计数:

public static int printKthToLast(LinkedListNode head, int k) {
    if (head == null) {
        return 0;
    }
    int index = printKthToLast(head.next, k) + 1;
    if (index == k) {
        System.out.println(k + "th to last node is " + head.data);
    }
    return index;
}

看:如果我想找出倒数第二项，而我的链表是{10，20，30，40}，答案是30.但是，如果每次迭代都添加索引，则索引将为(2)，然后结果为20.

我理解代码是(一些如何)从end开始的，这是有意义的，因为末尾第二项是30.但我不明白我从何说起"从头到尾".这是关于递归的一些东西，我还没有弄明白.

推荐答案

当你到达一个语句时，必须对其进行完整的判断，然后程序才能继续执行下一个语句.

对于方法，这意味着它们需要通过到达方法的末尾、return语句或引发异常来输入和返回.只有这样，包含方法调用的语句才被认为是"计算的".

现在，在您的 case 中，您拥有以下内容:

int index = printKthToLast(head.next, k) + 1;
if (index == k) {
    System.out.println(k + "th to last node is " + head.data);
}

首先是printKthToLast(head.next, k) + 1;，然后才打印结果.这意味着为了得到打印语句，必须对前面的语句进行完整的求值，这将启动递归链.

因此，流程是这样的:

printKthToLast(head.next, k)
|   printKthToLast(head.next.next, k)
|   |   printKthToLast(head.next.next.next, k)
|   |   |   ......
|   |   |   printKthToLast(head...next, k)
|   |   |   System.out.println(head...data) // innermost method, prints the last element
|   |   |   return index
|   |   |   ......
|   |   System.out.println(head.next.next.data)
|   |   return index
|   System.out.println(head.next.data)
|   return index
System.out.println(head.data)
return index

正如您所看到的，首先打印最后一个元素，然后实际完成最里面的方法，并返回到前面的方法，依此类推，直到您到达"最外面"的方法.