递归本身是一个特性吗? [英] Is recursion a feature in and of itself?

问题描述

...还是只是一种练习?

我问这个是因为和我的教授争论:我因为我们没有在课堂上介绍递归而失去了对递归调用函数的信任，我的论点是我们通过学习隐式地学习了它返回和方法.

我在这里问是因为我怀疑有人有明确的答案.

比如下面两种方法有什么区别:

public static void a() {返回一个();}公共静态无效 b() {返回一个();}

除了a一直持续下去"(在实际程序中，当提供无效输入时正确使用它来再次提示用户)，a之间有什么根本区别吗?code> 和 b?对于未优化的编译器，它们的处理方式有何不同?

最终归结为是否通过学习 return a() from b 我们也学会了 return a() from一个.是吗?

解决方案

回答您的具体问题:不，从学习语言的角度来看，递归不是一项功能.如果你的教授真的因为你使用了他还没有教过的功能"而扣分，那是错误的.

字里行间，一种可能性是通过使用递归，您可以避免使用本应成为课程学习成果的功能.例如，也许您根本没有使用迭代，或者您只使用了 for 循环，而不是同时使用 for 和 while.一项任务旨在测试您做某些事情的能力是很常见的，如果您避免这样做，您的教授就无法授予您为该功能留出的分数.然而，如果这真的是你失分的原因，教授应该把这当作他或她自己的学习经历——如果展示某些学习成果是作业的标准之一，应该向学生清楚地解释.

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

堆栈溢出

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

但是，要记住的一件事是，不仅是方法本身，调用链中更高或更低的其他方法都将在堆栈中.正因为如此，随便占用可用的堆栈空间对于任何方法来说都是非常不礼貌的事情.没有人愿意在编写代码时一直担心空闲堆栈空间，因为其他代码可能会不必要地使用大量空闲空间.

这是软件设计中称为抽象的更一般原则的一部分.本质上，当您调用 DoThing() 时，您只需要关心事物是否已完成.您不必担心如何完成的实现细节.但是贪婪地使用堆栈破坏了这一原则，因为每一位代码都必须担心它可以安全地假设调用链中其他地方的代码给它留下了多少堆栈.

可读性

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

private int getInput() {整数输入；做 {输入 = promptForInput();} while (!inputIsValid(input))返回输入；}

对比

private int getInput() {int input = promptForInput();if(inputIsValid(input)) {返回输入；}返回 getInput();}

是的，这两种方法都有效，而且它们都很容易理解.但是这两种方法如何用英语描述呢?我认为它会是这样的:

<块引用>

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

对比

<块引用>

我会提示输入，然后如果输入有效我会返回它，否则我会得到输入并返回结果

也许您可以为后者考虑稍微不那么笨拙的措辞，但我认为您总会发现第一个将在概念上更准确地描述您实际尝试做的事情.这并不是说递归总是可读性较差.对于它发光的情况，例如树遍历，您可以在递归和另一种方法之间进行相同类型的并排分析，并且您几乎肯定会发现递归提供的代码更清晰地逐行自我描述.

孤立地看，这两个都是小点.这不太可能真的导致堆栈溢出，而且可读性的提高很小.但任何计划都将是许多这些小决定的集合，因此即使孤立地它们并不重要，重要的是要了解使它们正确的背后的原则.

...or is it just a practice?

I'm asking this because of an argument with my professor: I lost credit for calling a function recursively on the basis that we did not cover recursion in class, and my argument is that we learned it implicitly by learning return and methods.

I'm asking here because I suspect someone has a definitive answer.

For example, what is the difference between the following two methods:

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?

Ultimately it comes down to whether by learning to return a() from b that we therefor also learned to return a() from a. Did we?

解决方案

To answer your specific question: No, from the standpoint of learning a language, recursion isn't a feature. If your professor really docked you marks for using a "feature" he hadn't taught yet, that was wrong.

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.

Having said that, I agree with most of the other comments and answers that iteration is a better choice than recursion here. There are a couple of reasons, and while other people have touched on them to some extent, I'm not sure they've fully explained the thought behind them.

Stack Overflows

The more obvious one is that you risk getting a stack overflow error. Realistically, the method you wrote is very unlikely to actually lead to one, since a user would have to give incorrect input many many times to actually trigger a stack overflow.

However, one thing to keep in mind is that not just the method itself, but other methods higher or lower in the call chain will be on the stack. Because of this, casually gobbling up available stack space is a pretty impolite thing for any method to do. Nobody wants to have to constantly worry about free stack space whenever they write code because of the risk that other code might have needlessly used a lot of it up.

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 how 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.

Readability

The other reason is readability. The ideal that code should aspire to is to be a human-readable document, where each line describes simply what it's doing. Take these two approaches:

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

Yes, these both work, and yes they're both pretty easy to understand. But how might the two approaches be described in English? I think it'd be something like:

I will prompt for input until the input is valid, and then return it

versus

I will prompt for input, then if the input is valid I will return it, otherwise I get the input and return the result of that instead

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 always 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.

In isolation, both of these are small points. It's very unlikely this would ever really lead to a stack overflow, and the gain in readability is minor. But any program is going to be a collection of many of these small decisions, so even if in isolation they don't matter much, it's important to learn the principles behind getting them right.

这篇关于递归本身是一个特性吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！