java - 为什么在Java链表遍历中使用递归不能返回Object？

Question

在 Cracking the Coding Interview(第 6 版)一书中，有一个问题要求我:

Implement an algorithm to find the the kth to last element of a singly linked list

后来，作者声称:

Unfortunately, we can't pass back a node and a counter using normal return statements.

她在上面的陈述中指的是Java语言。她后来表明，我们只能在 Java 中打印单向链表中的第 k 到最后一个元素。

我的问题是:为什么我们不能在递归弹出帧时传回一个节点？为什么我们不能向递归函数添加另一个参数，以便在正确的时间(即当 index = kth item 时)为我们正在寻找的节点设置该参数？从昨晚开始，我就一直在想这个问题，但我就是想不通。

提供的示例答案如下所示:

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;
}

Answer 1

当您说我们可以“向递归函数添加另一个参数以便在正确的时间设置参数”时，您是对的。例如，此功能的工作方式与您发布的解决方案相同:

private void printKthToLast(LinkedListNode head, int k, int index) {

    if(head == null) {
        return;
    }

    if(index >= k) {

        System.out.println(head.data);
    }

    printKthToLast(head.next, k, ++index);
}

我的猜测是作者试图说明递归通常“将问题分解为子问题，解决这些子问题，然后合并结果” (即经典的分而治之方法)。在这种情况下，当我们在“下一个”元素上调用递归函数时，将问题划分为子问题，因为我们越来越接近基本情况 (head == null) . 要组合的结果 是索引，它必须递归递增以确定何时必须打印节点。这就是索引建立函数返回类型 (int) 的原因。这是递归解决问题的正确方法。您的建议是有可能的，但是将“索引”作为参数传递既不是将问题划分为子问题，也不是合并结果。

此外，还需要考虑的是，在 Java 中，方法不仅通过名称来标识，还通过输入参数、返回类型等来标识。因此，这两个方法 ...

private int printKthToLast(LinkedListNode head, int k)

private void printKthToLast(LinkedListNode head, int k, int index)

... 是完全不同的，即使它们具有相同的名称(这称为多态性)。因此，将这两种方法包含在同一个解决方案中将不是递归。