为何Java递归方法printKthToLast从链表尾部开始计数？

我正在学习算法，目前被一个问题困扰许久。我理解递归的基本概念，但无法理解以下Java代码为何会从链表的尾部开始向前计数：

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}的倒数第2个元素，正确结果应为30。但如果按常规迭代时index递增的逻辑，index为2时对应的元素是20，这显然不对。我明白这段代码是从尾部开始计数的，但不清楚递归中哪部分实现了“从尾部开始”的逻辑。

核心逻辑解析 #

递归的关键在于调用栈的执行顺序——它是先“递”到链表尽头，再“归”回来计数：

1. 一开始调用printKthToLast(head, k)时，函数会一直调用自己处理下一个节点（head.next），直到head变成null（也就是走到了链表最后一个节点的下一个位置）。这时候第一个返回值是0。
2. 接下来进入回溯阶段：从链表的最后一个节点开始，往回逐个处理每个节点：
   • 最后一个节点（40）的递归调用会拿到前一步返回的0，加1后得到index=1，这就代表它是倒数第1个节点；
   • 回到前一个节点（30）时，拿到它下一个节点返回的index=1，加1得到index=2，刚好等于k=2，所以打印这个节点的数据；
   • 再往前的节点（20）会拿到index=2，加1变成3；节点（10）拿到3加1变成4，最终返回4。

说白了，常规迭代是从表头开始正着数，而递归的回溯过程是从表尾开始倒着数，这就是这段代码能找到倒数第k个元素的原因。

内容的提问来源于stack exchange，提问作者Lucas Bacciotti