我的幻灯片是这样说的:
递归调用应该总是在比当前调用更小的数据结构上
如果数据结构太小,必须有非递归的选项
您需要一个包装器方法来使递归方法可访问
仅从幻灯片中阅读此内容毫无意义,尤其是考虑到这是圣诞节前的主题!
谁能试着弄清楚这是什么意思?
谢谢
最佳答案
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();
关于java - 递归题: Revision,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2666717/