java - 递归题: Revision

Question

我的幻灯片是这样说的:

• 递归调用应该总是在比当前调用更小的数据结构上

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

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

仅从幻灯片中阅读此内容毫无意义，尤其是考虑到这是圣诞节前的主题!

谁能试着弄清楚这是什么意思？

谢谢

Answer 1

A recurssive call should always be on a smaller data structure than the current one

一般来说这不是真的，但如果你谈论的是使用递归的链表操作，那就是。这意味着您需要始终努力寻找解决方案，而这通常是在处理比您开始时更小的问题。

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

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

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

There must be a non recurssive option if the data structure is too small

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

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

You need a wrapper method to make the recurssive method accessible

我不了解 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();