如何在给定头节点的情况下递归地找到链表中的最大项？

Question

int findLargest (ListNode *p)
// --------------------------------------------------------------------------
// Preconditions: list head pointer is passed as a parameter.
// Postconditions: returns the largest value in the linked list.
// --------------------------------------------------------------------------
{
    if (p->item != NULL)
    {
        int largest = p->item;
        if (largest > p->next->item)
            ...
    }

    ...
}

是否可以编写这个递归函数只传递一个指针作为参数？如果不添加更多参数,我无法弄清楚如何做到这一点.有任何想法吗？我只使用顺序搜索.没有什么花哨.

以下是将要使用的类List的部分:

    struct ListNode 
    {
        ListItemType item;  // A data item on the list.
        ListNode    *next;  // Pointer to next node
    }; // end ListNode

    ListNode   *head; // Pointer to linked list of items.

我主要担心问题的可行性.这可以仅使用指针作为参数来完成吗？

Answer 1

虽然C不需要尾递归优化,但如果你可以将它转换为尾递归(并且你可以在这里完成很多工作),那么,当应用该优化时,你可以保持可读性,清晰度和具有与最佳非递归解决方案相同的性能(时间和空间)的递归的简洁性.

我稍微修改了函数的条件,因此它可以在没有节点的空列表上工作(其中p为null),在这种情况下将返回null.这是尾递归,并且需要另一个参数:

ListNode* findLargestRecurse(ListNode* p, ListNode* largest) {
  // this is an implementation detail, and would not be called directly
  // requires that largest is not null, but p may be null
  if (!p) return largest;
  if (p->item > largest->item) largest = p;
  return findLargestRecurse(p->next, largest);
}

// preconditions: list head pointer is passed as a parameter, and may be null
// postcondition: returns the node with the largest value, or null
ListNode* findLargest(ListNode* p) {
  if (!p) return 0; // mark A, see below
  return findLargestRecurse(p->next, p);
}

请注意,您使用主条目findLargest来设置实际递归的初始条件/上下文findLargestRecurse.

但是,我将尾递归写成一个迭代的while循环,以减少对C目前非常特定的编译器和通常不熟悉的东西的依赖,这并不难:

// preconditions: list head pointer is passed as a parameter, and may be null
// postcondition: returns the node with the largest value, or null
ListNode* findLargest(ListNode* p) {
  ListNode* largest = 0;
  for (; p; p = p->next) {
    if (!largest || p->item > largest->item) {
      largest = p;
    }
  }
  return largest;
}

你可以!largest事先通过检查一个基本案例,就像第一个findLargest那样("标记A"),将条件从循环中分离出来.

现在看看这个,你可能想知道为什么我把递归版本称为更简洁:它真的不适合这个简单的例子.这部分是因为C被设计为有利于迭代(特别注意for循环),有点因为我试图在递归中变得冗长而不是像往常一样压扁它(所以你可以更容易理解),其余的是因为这只是一个简单的问题.