递归问：修订

Question

我的幻灯片说：

• 递归调用应该永远是比当前的

• 必须有一个非递归如果数据结构选择一个较小的数据结构太小

• 您需要的包装方法，使访问的递归方法

只需从幻灯片中阅读这些内容是没有意义的，尤其是看到它是圣诞节前的话题！

任何人都可以尝试清理它意味着什么吗？

谢谢

Answer 1

一个recurssive调用应始终在一个较小的数据结构比当前

一般来说，这是不正确的，但如果你是在谈论链表与操纵它是递归的。这意味着你需要始终努力寻求一种解决方案，而这通常是处理比你开始时更小的问题。

以Quicksort为例。每次调用该函数时，都会使用一组较小的数据。

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

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

必须有一个非recurssive选项，如果所述数据结构是太小

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

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

您需要的包装方法，使访问的recurssive方法

我不知道Java的，它是不是一个真正的语言是为递归设计的，但是在许多情况下，递归函数的参数比使用API​​的人应该能够看到的参数多。例如，你可能想在那里有一个柜台。

你可以有一个包装函数，它可以简化参数，只是需要什么。包装函数然后调用真正的工作者函数。

一个例子可能是如果我们有一个链表类，它具有递归函数来打印列表。使用API​​它并没有太大的SENCE

void printList(List l); 

然而，因为它是一个类的方法，就有人来要做到这一点：它的声明会是这个样子

myList.printList(myList); 

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

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

然后，所有使用API​​的程序员所要做的就是：

myList.printList();