递归问题：修订

Question

我的幻灯片说：

• 递归调用应始终在比当前数据结构更小的数据结构上

• 必须有一个非如果数据结构太小，则采用递归选项

• 您需要一个包装方法来使递归方法可访问

仅从幻灯片中阅读此内容是没有意义的，特别是考虑到这是圣诞节前的主题！

有人可以尝试弄清楚这意味着什么吗？

谢谢

Answer 1

递归调用应始终使用比当前数据结构更小的数据结构

一般来说，这是不正确的，但如果您正在谈论带有递归的链表操作，则事实如此。这意味着您需要始终努力寻求解决方案，而这通常是在处理比开始时更小的问题。

以快速排序为例。每次调用该函数时，它都会处理较小的数据集。

再举一个打印链表的例子，下次调用递归函数时，参数应该是链表的尾部（这段代码有一个错误，但这引导我们到下一点）

void printList(List l){
    print(l.head);
    printList(l.tail); 
}

如果数据结构太小，必须有非递归选项

这意味着应该有一个基本情况。函数再次停止调用自身的点。

int factorial(int n){
    if ( n == 1 ){ //the base case is when n = 1
        return 1;
    }
    return n*factorial(n-1);
}

回到打印链接列表的示例，必须有一种情况，您只剩下一个空列表（在这种情况下，该函数应该不执行任何操作）。回到打印链表的代码

void printList(List l){
    if ( l.empty == true ){ //the base case is when the list l is empty
        return;
    }

    print(l.head);
    printList(l.tail); 
}

您需要一个包装方法来使递归方法可访问

我不懂Java，而且它并不是真正为递归设计的语言，但是在许多情况下，你的递归函数将具有比使用API​​的人应该能够承受的参数更多的参数查看。例如，您可能希望在那里有一个柜台。

您可以拥有一个包装函数，将参数简化为所需的参数。然后包装函数调用真正的工作函数。

一个例子是，如果我们有一个链表类，它具有打印列表的递归函数。它的声明看起来像这样：

void printList(List l);

然而，由于它是一个类方法，对于使用 API 的人来说，这样做没有多大意义：

myList.printList(myList);

因此可以创建一个没有任何参数的包装函数，然后调用完成工作的代码。

void printList(){
     doPrintList(this); //pass in the List object as the first argument
}

那么使用 API 的程序员所要做的就是：

myList.printList();