java - Java中的链表递归

Question

我必须编写一个递归方法，该方法迭代链接列表并返回正整数的数量。问题如下:

下面的方法 countPos 必须是一个采用 Node 头的递归方法 作为其参数，沿着以 head 为首的列表向下移动，并计算具有正数据字段的节点的数量。

我的代码可以工作，但是我不明白它是如何工作的。

public int countPos(Node head) {
    int count = 0; 
    if (head == null) { return count; }

    if (head.data > 0) {
        count++; 
        return count + countPos(head.next);
    } else {
        return count + countPos(head.next);
    }
}

我遇到的问题是我不明白每次调用该方法时 count 为何不设置回 0。由于某种原因，下次调用该方法时，语句 int count = 0; 将被忽略。这是因为我也返回了 count 吗？任何解释将不胜感激。

谢谢。

Answer 1

不要从跟踪执行或调试开始。递归的强大之处在于它可以让您用简单的逻辑推理复杂的程序。

你的代码是偶然工作的。这反射(reflect)出无论是谁写的(你？)都不明白递归是如何解决问题的。它比必要的更复杂。

要利用递归，请解决当前的问题:

1. 定义函数接口(interface)。
2. 将问题分成几个部分，至少其中一个是同一问题的较小版本。
3. 通过调用函数接口(interface)本身来解决该(或那些)较小版本的问题。
4. 找到“基本案例”或针对同一问题的极小实例的解决方案。

完成这一切后，大多数递归算法的伪代码是:

function foo(args)

   if args describe a base case
     return the base case answer.

   solve the smaller problem or problems by calling foo with 
     args that describe the smaller problem!

   use the smaller problem solution(s) to get the answer for this set of args

   return that answer
end

让我们将其应用到您的案例中:

问题:计算列表中正项的数量。

1. 定义函数接口(interface):int countPos(Node head)。
2. 将问题分成几个部分:获取列表中在头部之后剩余的正数，然后如果头部为正则加一，如果头部为零或负则不添加任何内容。
3. 问题的较小版本是查找列表中删除头的正数的数量:countPos(head.next)。
4. 找到基本情况:空列表的正值为零。

把这些放在一起:

int countPos(Node head) {

  // Take care of the base case first.
  if (head == null) return 0;

  // Solve the smaller problem.
  int positiveCountWithoutHead = countPos(head.next);

  // Now the logic in step 2. Return either the positive count or 1+ the positive count:
  return head.data > 0 ? positiveCountWithoutHead + 1 : positiveCountWithoutHead;
}

您可能可以通过跟踪类似这样的事情的执行一次来学到一点东西。但是尝试通过推理堆栈发生的情况来编写递归代码是一个死胡同。要想成功，你必须站在更高的层次思考。

让我们尝试一个不太遵循标准模板的方法:递归二分搜索。我们有一个整数数组 a，并尝试查找 x 的索引(如果它存在于数组中)，如果不存在则返回 -1。

问题:在位置 i0 和 i1-1 之间搜索数组。

(上面是一个示例，说明有时必须通过添加参数来“专门化”问题，以便可以在一个或多个递归调用中描述较小的子问题。这里我们添加新参数i0 和 i1，以便我们可以指定 a 的子数组。知道如何以及何时执行此操作是一个实践问题。所需的参数可能会因语言特性而异。)

1. 函数接口(interface):int search(int [] a, int x, int i0, int i1)
2. 将问题分成几部分:我们将选择一个“中间”元素索引:mid = (i0 + i1)/2。那么子问题要么搜索数组的前半部分，直到 mid 但不包括 mid，要么搜索数组的后半部分，从 mid 之后开始一直持续到末尾。
3. 调用为 search(a, x, i0, mid) 和 search(a, x, mid + 1, i1)。
4. 基本情况是 1) 如果 i0 >= i1，则没有要搜索的元素，因此返回 -1 和 2) 如果我们有 a[mid] == x，那么我们找到了x并且可以返回mid。

把这些放在一起

int search(int [] a, int x, int i0, int i1) {

  // Take care of one base case.
  if (i0 >= i1) return -1;

  // Set up mid and take care of the other base case.
  int mid = (i0 + i1) / 2;
  if (a[mid] == x) return mid;

  // Solve one or the other subproblems.  They're both smaller!
  return x < a[mid] ? search(a, x, i0, mid) : search(a, x, mid + 1, i1);
}

并开始搜索:

int search(int [] a, int x) { return search(a, x, 0, a.length); }