116 recursion
......还是只是一种做法？
我问这个是因为与我的教授争吵:我因为我们没有在课堂上报道递归而递归调用一个函数而失去了信誉,我的论点是我们通过学习return和方法隐式地学习它.
我在这里问,因为我怀疑有人有明确的答案.
例如,以下两种方法有什么区别:
public static void a() {
return a();
}
public static void b() {
return a();
}
除了" a永远长存"(在实际的程序是正确使用时输入的内容无效,再次提示用户),有没有之间的任何根本区别a和b？对于未经优化的编译器,它们如何以不同方式处理？
归根结底,通过学习可以归结为是否return a()从b我们为此还学会了return a()从a.我们呢？
Ben*_*son 112
回答你的具体问题:不,从学习语言的角度来看,递归不是一个特征.如果你的教授确实停靠了你使用他尚未教过的"特征"的标记,那就错了.
在线之间阅读,一种可能性是通过使用递归,你避免使用一个本来应该是他的课程学习成果的特征.例如,也许您根本没有使用迭代,或者您可能只使用for循环而不是同时使用for和while.通常,作业旨在测试你做某些事情的能力,如果你避免这样做,你的教授根本无法授予你为该特征留出的标记.然而,如果这真的是你失去分数的原因,那么教授应该把这作为他或她自己的学习经历 - 如果证明某些学习成果是作业的标准之一,应该向学生清楚地解释.
话虽如此,我同意大多数其他评论和答案,迭代是一个比递归更好的选择.有几个原因,虽然其他人在某种程度上触及了它们,但我不确定他们是否完全解释了他们背后的想法.
堆栈溢出
更明显的一个是你冒着堆栈溢出错误的风险.实际上,您编写的方法实际上不太可能导致一个方法,因为用户必须多次提供错误的输入才能实际触发堆栈溢出.
但是,要记住的一件事是,不仅方法本身,而且调用链中更高或更低的其他方法将在堆栈上.因此,随意吞噬可用的堆栈空间对于任何方法来说都是非常不礼貌的事情.没有人希望在编写代码时不得不经常担心空闲堆栈空间,因为其他代码可能不必要地使用了很多代码.
这是称为抽象的软件设计中更一般原则的一部分.从本质上讲,当你打电话时DoThing(),你需要关心的是事情已经完成了.你不应该担心它是如何完成的实现细节.但是贪婪地使用堆栈破坏了这个原则,因为每一段代码都必须担心它可以安全地假设它有多少堆栈由调用链中其他地方的代码留给它.
可读性
另一个原因是可读性.代码应该追求的理想是成为一个人类可读的文档,其中每一行简单地描述它正在做什么.采取以下两种方法:
private int getInput() {
int input;
do {
input = promptForInput();
} while (!inputIsValid(input))
return input;
}
与
private int getInput() {
int input = promptForInput();
if(inputIsValid(input)) {
return input;
}
return getInput();
}
是的,这些都有效,是的,它们都很容易理解.但这两种方法怎么用英语描述呢？我认为它是这样的:
我将提示输入,直到输入有效,然后返回它
与
我将提示输入,然后如果输入有效,我将返回它,否则我得到输入并返回该结果
也许你可以想到后者的措辞略显笨拙,但我认为你总会发现第一个是概念性地描述你实际上想做的事情.这并不是说递归总是不太可读.对于像树遍历那样闪耀的情况,你可以在递归和另一种方法之间进行相同类型的并排分析,并且你几乎肯定会发现递归会给出代码,这些代码更直接地逐行自我描述.
孤立地说,这两点都是小点.这种情况不太可能真正导致堆栈溢出,并且可读性的提高很小.但是任何程序都将成为许多这些小决策的集合,因此即使孤立无关,它们也无关紧要,因此学习正确理解背后的原则非常重要.
Har*_*ton 48
回答文字问题,而不是元问题:递归是一个特征,在某种意义上并非所有编译器和/或语言都必然允许它.在实践中,它应该是所有(普通的)现代编译器 - 当然还有所有Java编译器!- 但这并不普遍.
作为可能不支持递归的设想示例,请考虑将函数的返回地址存储在静态位置的编译器; 例如,对于没有堆栈的微处理器的编译器可能就是这种情况.
对于这样的编译器,当你调用这样的函数时
a();
它被实现为
move the address of label 1 to variable return_from_a
jump to label function_a
label 1
和()的定义,
function a()
{
var1 = 5;
return;
}
实现为
label function_a
move 5 to variable var1
jump to the address stored in variable return_from_a
希望在尝试a()在这样的编译器中递归调用时出现问题是显而易见的; 编译器不再知道如何从外部调用返回,因为返回地址已被覆盖.
对于我实际使用的编译器(我认为是70年代末或80年代早期),不支持递归,问题比这更微妙:返回地址将存储在堆栈中,就像在现代编译器中一样,但局部变量不是"T.(从理论上讲,这应该意味着对于没有非静态局部变量的函数可以进行递归,但我不记得编译器是否明确支持它.由于某种原因,它可能需要隐式局部变量.)
展望未来,我可以想象专门的场景 - 可能是大量并行系统 - 不必为每个线程提供堆栈可能是有利的,因此只有在编译器可以将其重构为循环时才允许递归.(当然,我上面讨论的原始编译器不能完成复杂的任务,比如重构代码.)
mik*_*ike 17
老师想知道你是否学过.显然你没有按照他教你的方式解决问题(好方法 ;迭代),因此,认为你没有.我都是创造性的解决方案,但在这种情况下,我必须与你的老师达成一致,原因不同:
如果用户提供的输入次数过多(即按住Enter键),你将遇到堆栈溢出异常并且你的解决方案会崩溃.此外,迭代解决方案更高效,更易于维护.我认为这就是你的老师应该给你的原因.
gna*_*729 13
因为"我们没有在课堂上报道递归"而导致的分数很糟糕.如果你学会了如何调用函数A,它调用函数B调用函数C,函数C返回给B,返回给A返回给调用者,而老师没有明确告诉你这些必须是不同的函数(例如,在旧的FORTRAN版本中就是这种情况,没有理由A,B和C不能都是相同的功能.
另一方面,我们必须看到实际的代码来决定在你的特定情况下使用递归是否真的是正确的事情.没有太多细节,但确实听起来不对.
Yon*_*Nir 10
关于您提出的具体问题,有很多观点可以看,但我可以说的是,从学习语言的角度来看,递归本身并不是一个特征.如果你的教授确实停靠了你使用他尚未教过的"特征"的标记,那就错了,但就像我说的那样,这里还有其他观点要考虑,这实际上使教授在扣除积分时是对的.
从我可以推断出你的问题,使用递归函数在输入失败的情况下请求输入不是一个好习惯,因为每个递归函数的调用都被推送到堆栈.由于这种递归是由用户输入驱动的,因此可以具有无限递归函数,从而产生StackOverflow.
在你的问题中你提到的这两个例子之间没有区别(但在其他方面有所不同) - 在这两种情况下,返回地址和所有方法信息都被加载到堆栈中.在递归的情况下,返回地址就是调用方法之后的那一行(当然它不完全是你在代码本身看到的,而是在编译器创建的代码中).在Java,C和Python中,与迭代(通常)相比,递归相当昂贵,因为它需要分配新的堆栈帧.更不用说如果输入无效太多,你可以获得堆栈溢出异常.
我相信教授会扣除分数,因为递归被认为是它自己的主题,不太可能没有编程经验的人会想到递归.(当然,这并不意味着他们不会,但不太可能).
恕我直言,我认为教授是正确的,通过扣除你的积分.您可以轻松地将验证部分用于其他方法并使用它如下:
public bool foo()
{
validInput = GetInput();
while(!validInput)
{
MessageBox.Show("Wrong Input, please try again!");
validInput = GetInput();
}
return hasWon(x, y, piece);
}
如果你所做的确实能以这种方式解决,那么你所做的是一种不好的做法,应该避免.
也许你的教授还没有教过它,但听起来你已经准备好了解递归的优点和缺点.
递归的主要优点是递归算法通常更容易和更快速地编写.
递归的主要缺点是递归算法会导致堆栈溢出,因为每个递归级别都需要将额外的堆栈帧添加到堆栈中.
对于生产代码,其中缩放可以导致生产中的递归级别比程序员的单元测试中更多级别,但缺点通常超过优势,并且在实际应用中通常会避免使用递归代码.
关于具体问题,递归是一个特征,我倾向于说是,但在重新解释问题之后.语言和编译器的共同设计选择使得递归成为可能,并且存在完全不允许递归的图灵完备语言.换句话说,递归是由语言/编译器设计中的某些选择启用的能力.
支持一流函数可以在非常小的假设下实现递归; 请参阅Unlambda中的循环编写示例,或者这个不包含自引用,循环或赋值的钝化Python表达式:
>>> map((lambda x: lambda f: x(lambda g: f(lambda v: g(g)(v))))(
... lambda c: c(c))(lambda R: lambda n: 1 if n < 2 else n * R(n - 1)),
... xrange(10))
[1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]
使用后期绑定或定义前向声明的语言/编译器可以使递归成为可能.例如,虽然Python允许以下代码,但这是一个设计选择(后期绑定),而不是对图灵完备系统的要求.相互递归函数通常依赖于对前向声明的支持.
factorial = lambda n: 1 if n < 2 else n * factorial(n-1)
允许递归定义类型的静态类型语言有助于启用递归.在Go中查看Y Combinator的这个实现.如果没有递归定义的类型,仍然可以在Go中使用递归,但我相信Y组合器是不可能的.
从我可以从你的问题中推断出,在输入失败的情况下使用递归函数来请求输入不是一个好习惯.为什么？
因为每个递归函数调用都会被推送到堆栈.由于此递归由用户输入驱动,因此可以具有无限递归函数,从而产生StackOverflow :-p
有一个非递归循环来做到这一点是要走的路.