递归本身就是一个功能吗?
......还是仅仅是一种练习?
我是这样问的,因为和我的教授发生了争执:因为我们没有涉及到课堂递归,所以我们递归地调用一个函数失去了功劳,我的观点是我们通过学习return
和方法隐含地学到了它。
我在这里问,因为我怀疑有人有一个明确的答案。
例如,以下两种方法有什么区别:
public static void a() {
return a();
}
public static void b() {
return a();
}
除了“ a
永续”(在实际的程序是正确使用时输入的内容无效,再次提示用户),有之间的根本区别a
和b
? 对于未优化的编译器,它们的处理方式有何不同?
最终归结为是否通过学习从b
return a()
,我们也学会了从a
return a()
。 我们?
回答你的具体问题:不,从学习语言的角度来看,递归不是一个特征。 如果你的教授真的使用他还没有教过的“特征”来标记你的标记,那就错了。
在这两行之间进行阅读,有一种可能性是,通过使用递归,你避免了使用本应该是学习成果的功能。 比如,也许你没有使用迭代可言,或者你只用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();
}
是的,这两个都有效,而且它们都很容易理解。 但这两种方法怎么可能用英文来描述呢? 我认为它会是这样的:
我会提示输入,直到输入有效,然后返回
与
我会提示输入,然后如果输入有效,我会返回它,否则我会得到输入并返回结果
也许你可以想到后者的粗略措辞,但我想你会发现第一个从概念上来说是一个更准确的描述,即你实际要做的事情。 这并不是说递归总是不太可读。 对于像树遍历一样的情况,你可以在递归和其他方法之间进行同样的并行分析,你几乎肯定会发现递归给出的代码更清晰,逐行地自我描述。
孤立地说,这些都是小点。 这是不太可能导致堆栈溢出的,并且可读性的提高很小。 但是任何程序都将成为许多这些小决策的集合,所以即使孤立它们并不重要,重要的是要了解让它们正确的原则。
为了回答文字问题,而不是元问题:递归是一个特征,因为并非所有编译器和/或语言都必须允许它。 实际上,它是所有(普通)现代编译器的预期 - 当然也包括所有的Java编译器! - 但它并不普遍。
作为可能不支持递归的一个人为的例子,考虑一个将函数的返回地址存储在静态位置的编译器; 例如,对于没有堆栈的微处理器的编译器,情况可能如此。
对于这样的编译器,当你调用这样的函数时
a();
它被实现为
move the address of label 1 to variable return_from_a
jump to label function_a
label 1
和a()的定义,
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。 (理论上这应该意味着对于没有非静态局部变量的函数,递归是可能的,但是我不记得编译器是否明确地支持这个变量,出于某种原因它可能需要隐式局部变量。)
展望未来,我可以想象专门的场景 - 大量并行的系统,也许 - 不必为每个线程提供堆栈都可能是有利的,因此只有编译器可以将其重构为循环时才允许递归。 (当然,我上面讨论的原始编译器不能处理重构代码等复杂任务。)
老师想知道你是否学过。 显然,你没有像他教你的方式解决问题(好方法;迭代),因此,认为你没有。 我都是为了创造性的解决方案,但在这种情况下,我不得不同意你的老师出于不同的原因:
如果用户提供无效输入的次数过多(即通过保持输入按下),您将遇到堆栈溢出异常,您的解决方案将崩溃。 另外,迭代解决方案更加高效且易于维护。 我认为这是你的老师应该给你的原因。