递归问题:修订

Question

我的幻灯片说:

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

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

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

从幻灯片中读取这些内容毫无意义,尤其是看到它是圣诞节前的主题!

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

谢谢

Answer 1

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

一般情况下这不是真的,但如果你正在谈论链接列表操作与递归它是.这意味着你需要始终致力于解决方案,这通常是处理比你开始时更小的问题.

以Quicksort为例.每次调用该函数时,它都使用较小的数据集.

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

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

您需要一个包装器方法来使recursiveive方法可访问

我不了解Java,它实际上并不是一种为递归设计的语言,但是在很多情况下,递归函数的参数比使用API​​的人应该能够看到的参数多.例如,你可能希望在那里有一个计数器.

您可以使用包装函数将参数简化为所需的参数.然后包装函数调用真正的worker函数.

一个例子可能是我们有一个链表类,它具有打印列表的递归函数.它的声明看起来像这样:

void printList(List l);

但是因为它是一个类方法,对于使用API​​的人来说,它不需要做很多事情:

myList.printList(myList);

因此,可以创建一个包装函数,该函数没有任何参数,然后调用执行该工作的代码.

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

然后使用API​​的所有程序员必须做的是:

myList.printList();