递归本身是一个特性吗？

还是只是练习？

我问这个问题是因为我和教授的一个争论: 我失去了在课堂上没有涉及到递归的基础上递归调用函数的信誉，我的争论是我们通过学习 return和方法隐式地学习了递归。

我这么问是因为我怀疑有人能给出明确的答案。

例如，以下两种方法的区别是什么:

public static void a() {
return a();
}


public static void b() {
return a();
}

Other than "a continues forever" (in the actual program it is used correctly to prompt a user again when provided with invalid input), is there any fundamental difference between a and b? To an un-optimized compiler, how are they handled differently?

归根结底，是否通过从 b学习到 return a()，我们也因此从 a学习到 return a()。有吗？

6337 次浏览
小开

There are many point of views to look at regarding the specific question you asked but what I can say is that from the standpoint of learning a language, recursion isn't a feature on its own. If your professor really docked you marks for using a "feature" he hadn't taught yet, that was wrong but like I said, there are other point of views to consider here which actually make the professor being right when deducting points.

From what I can deduce from your question, using a recursive function to ask for input in case of input failure is not a good practice since every recursive functions' call gets pushed on to the stack. Since this recursion is driven by user input it is possible to have an infinite recursive function and thus resulting in a 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);
}

如果你所做的确可以用这种方式解决，那么你所做的就是一种不好的做法，应该避免。

小开

从你的问题中我可以推断出，在输入失败的情况下使用递归函数请求输入并不是一个好的做法。为什么？

因为每个递归函数调用都会被推送到堆栈上。由于这种递归是由用户输入驱动的，因此可以有一个无限的递归函数，从而产生一个 StackOverflow 堆栈溢出:-p

Having a non recursive loop to do this is the way to go.

小开

老师想知道你有没有学习。显然，你没有按照他教你的方法(好的方式; 迭代)解决问题，因此，认为你没有。我完全赞成创造性的解决方案，但是在这种情况下，我不得不同意你老师的观点，因为另一个原因: < br > 如果用户提供了太多次无效的输入(比如按回车键) ，那么你的解决方案就会出现堆栈溢出异常，并且崩溃。此外，迭代解决方案更有效，更容易维护。我想这就是你老师应该给你的理由。

小开

因为“我们在课堂上没有讲到递归”而扣分是很糟糕的。如果你学会了如何调用函数 A，它调用函数 B，它调用函数 C，它返回给 B，它返回给 A，它返回给调用者，并且老师没有明确地告诉你这些必须是不同的函数(例如在旧的 FORTRAN 版本中就是这种情况) ，那么没有理由说 A，B 和 C 不可能都是同一个函数。

另一方面，我们必须看到实际的代码，以确定在您的特定情况下使用递归是否真的是正确的做法。没有太多细节，但听起来确实不对。

小开

也许你的教授还没有教过它，但是听起来你已经准备好学习递归的优缺点了。

递归的主要优点是，递归算法通常更容易、更快速地编写。

The main disadvantage of recursion is that recursive algorithms can cause stack overflows, since each level of recursion requires an additional stack frame to be added to the stack.

对于产品代码，比起程序员的单元测试，缩放在产品中会导致更多的递归级别，这样做的弊大于利，而且在实际应用中经常避免使用递归代码。

小开
最佳答案

回答你的具体问题: 不，从学习语言的角度来看，递归不是一个特性。如果你的教授真的因为你使用了他还没有教过的“功能”而扣分，那就错了。

Reading between the lines, one possibility is that by using recursion, you avoided ever using a feature that was supposed to be a learning outcome for his course. For example, maybe you didn't use iteration at all, or maybe you only used for loops instead of using both for and while. It's common that an assignment aims to test your ability to do certain things, and if you avoid doing them, your professor simply can't grant you the marks set aside for that feature. However, if that really was the cause of your lost marks, the professor should take this as a learning experience of his or her own- if demonstrating certain learning outcomes is one of the criteria for an assignment, that should be clearly explained to the students.

尽管如此，我同意大多数其他评论和回答，迭代在这里是比递归更好的选择。有几个原因，虽然其他人已经在某种程度上接触到它们，我不确定他们已经完全解释了背后的想法。

堆栈溢出

更明显的是，您可能会得到一个堆栈溢出错误。实际上，您编写的方法不太可能实际导致堆栈溢出，因为用户必须多次输入错误才能实际触发堆栈溢出。

但是，需要记住的一点是，不仅方法本身，而且调用链中位置更高或更低的其他方法都将位于堆栈上。因此，随意地占用可用堆栈空间对于任何方法来说都是非常不礼貌的。没有人希望在编写代码时不断地担心空闲堆栈空间，因为其他代码可能不必要地使用了大量空闲堆栈空间。

This is part of a more general principle in software design called abstraction. Essentially, when you call DoThing(), all you should need to care about is that Thing is done. You shouldn't have to worry about the implementation details of 怎么做 it's done. But greedy use of the stack breaks this principle, because every bit of code has to worry about how much stack it can safely assume it has left to it by code elsewhere in the call chain.

可读性

另一个原因是可读性。代码应该追求的理想状态是成为一个人类可读的文档，其中每一行简单地描述了它在做什么。采取以下两种方法:

private int getInput() {
int input;
do {
input = promptForInput();
} while (!inputIsValid(input))
return input;
}

versus

private int getInput() {
int input = promptForInput();
if(inputIsValid(input)) {
return input;
}
return getInput();
}

是的，这两个都有用，而且它们都很容易理解。但是如何用英语来描述这两种方法呢？我想应该是这样的:

我将提示输入，直到输入有效，然后返回它

VS

我将提示输入，然后如果输入是有效的，我将返回它，否则我将获得输入并返回结果

Perhaps you can think of slightly less clunky wording for the latter, but I think you'll always find that the first one is going to be a more accurate description, conceptually, of what you are actually trying to do. This isn't to say recursion is 一直都是 less readable. For situations where it shines, like tree traversal, you could do the same kind of side by side analysis between recursion and another approach and you'd almost certainly find recursion gives code which is more clearly self-describing, line by line.

单独来看，这两个问题都是小问题。这不太可能真正导致堆栈溢出，而且可读性的提高很小。但是任何一个程序都将是这些小决策的集合，所以即使它们孤立地无关紧要，重要的是要学会正确做决策背后的原则。

小开

为了回答文字问题，而不是元问题: 递归 是是一个特性，因为并非所有的编译器和/或语言都必须允许它。实际上，所有(普通)现代编译器都希望使用它，当然也包括所有 Java 编译器！但它不是 全世界真实的。

As a contrived example of why recursion might not be supported, consider a compiler that stores the return address for a function in a static location; this might be the case, for example, for a compiler for a microprocessor that does not have a stack.

对于这样的编译器，当您调用这样的函数时

a();

it is implemented as

move the address of label 1 to variable return_from_a
jump to label function_a
label 1

and the definition of 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年代初) ，它不支持递归，这个问题比这个稍微微微妙一点: 返回地址会存储在堆栈上，就像现代编译器一样，但局部变量不会。(理论上这应该意味着递归对于没有非静态局部变量的函数是可能的，但是我不记得编译器是否明确支持这一点。出于某种原因，它可能需要隐式局部变量。)

展望未来，我可以想象专门的场景——可能是高度并行的系统——不必为每个线程提供堆栈可能是有利的，因此只有在编译器能够将其重构为循环时才允许递归。(当然，我上面讨论的基本编译器不能完成像重构代码这样的复杂任务。)

小开

关于特定的问题，递归是一个特性吗，我倾向于说是的，但是在重新解释这个问题之后。使递归成为可能的语言和编译器有很多通用的设计选择，而且图灵完成语言确实存在 根本不允许递归。换句话说，递归是一种由语言/编译器设计中的某些选择所启用的能力。

  • 支持 一级函数使得递归在极少的假设条件下成为可能; 参见 用 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]

  • Languages/compilers that use late binding, or that define forward declarations, make recursion possible. For example, while Python allows the below code, that's a design choice (late binding), not a requirement for a Turing-complete system. Mutually recursive functions often depend on support for forward declarations.

    factorial = lambda n: 1 if n < 2 else n * factorial(n-1)

  • Statically typed languages that allow recursively defined types contribute to enabling recursion. See this implementation of the Y Combinator in Go. Without recursively-defined types, it would still be possible to use recursion in Go, but I believe the Y combinator specifically would be impossible.

小开

递归 是一个编程 概念、一个 特写(类似迭代)和一个 练习。正如你可以从链接中看到的，有一个很大的研究领域致力于这个主题。也许我们不需要深入这个话题来理解这些观点。

作为特性的递归

简单地说，Java 隐式地支持它，因为它允许一个方法(基本上是一个特殊的函数)拥有关于它自己和组成它所属类的其他方法的“知识”。考虑一种不是这种情况的语言: 您可以编写该方法 a的主体，但是不能在其中包含对 a的调用。唯一的解决方案是使用迭代来获得相同的结果。在这样的语言中，您必须区分那些知道自己存在的函数(通过使用特定的语法标记)和那些不知道它们存在的函数！实际上，一组语言确实做出了这种区分(例如，请参阅 口齿不清和 ML系列)。有趣的是，Perl 甚至允许匿名函数(所谓的 Lambdas)递归地调用它们自己(同样，使用专门的语法)。

没有递归？

对于那些甚至不支持递归的语言，通常还有另一种解决方案，即 Fixed-point combinator，但它仍然需要语言支持所谓的第一类对象(即可以在语言本身内操作的对象)。

作为实践的递归

在一种语言中拥有这种特性并不意味着它是惯用的。在 Java8中，已经包含了 lambda 表达式，因此采用函数式方法进行编程可能会变得更加容易。然而，也有一些实际的考虑:

  • 语法仍然不是很友好的递归
  • 编译器可能无法检测到这种做法和 优化它

这是底线

幸运的是(或者更准确地说，为了方便使用) ，Java 默认允许方法自我识别，因此支持递归，所以这不是一个真正的实际问题，但它仍然是一个理论问题，我想你的老师想要特别解决这个问题。此外，鉴于最近语言的演变，它可能在未来变成一些重要的东西。


提交答案