什么是递归，什么时候应该使用它？ [英] What is recursion and when should I use it?

问题描述

似乎经常出现在邮件列表和在线讨论中的主题之一是获得计算机科学学位的优点（或缺乏优点）。对于否定党来说，似乎反复出现的一个论点是，他们已经编码了多年，并且他们从未使用过递归。

One of the topics that seems to come up regularly on mailing lists and online discussions is the merits (or lack thereof) of doing a Computer Science Degree. An argument that seems to come up time and again for the negative party is that they have been coding for some number of years and they have never used recursion.

所以这个问题是：

1. 什么是递归？


2. 何时使用递归？


3. 为什么人们不使用递归？

推荐答案

在此线程中递归的正确解释的数量，此答案是关于您为什么不应该这样做的原因在大多数语言中都不要使用它。*在大多数主要命令式语言实现中（即C，C ++，Basic，Python，Ruby，Java和C＃的每个主要实现）迭代远胜于递归。

There are a number of good explanations of recursion in this thread, this answer is about why you shouldn't use it in most languages.* In the majority of major imperative language implementations (i.e. every major implementation of C, C++, Basic, Python, Ruby,Java, and C#) iteration is vastly preferable to recursion.

要了解原因，请按照上述步骤操作语言用于调用函数：

To see why, walk through the steps that the above languages use to call a function:

$ b在函数的参数和局部变量的堆栈上切出了$ b
1. 空间 li>
   
2. 将函数的参数复制到该新空间中


3. 控件跳转到该函数


4. 该函数的代码运行


5. 将该函数的结果复制到一个返回值中


6. 将堆栈退回到其栈中上一个位置


7. 控件跳回到调用该函数的位置

1. space is carved out on the stack for the function's arguments and local variables
2. the function's arguments are copied into this new space
3. control jumps to the function
4. the function's code runs
5. the function's result is copied into a return value
6. the stack is rewound to its previous position
7. control jumps back to where the function was called

执行所有这些步骤需要时间，通常比遍历一个循环要花费更多时间。但是，真正的问题是在步骤1中。当许多程序启动时，它们会为其堆栈分配一个内存块，并且当它们用完该内存时（通常但并非总是由于递归），由于堆栈溢出。

Doing all of these steps takes time, usually a little bit more than it takes to iterate through a loop. However, the real problem is in step #1. When many programs start, they allocate a single chunk of memory for their stack, and when they run out of that memory (often, but not always due to recursion), the program crashes due to a stack overflow.

因此，在这些语言中，递归速度较慢，因此您很容易受到攻击崩溃。虽然仍然有一些使用它的争论。通常，一旦您知道如何阅读，递归编写的代码就会更短，更优雅。

So in these languages recursion is slower and it makes you vulnerable to crashing. There are still some arguments for using it though. In general, code written recursively is shorter and a bit more elegant, once you know how to read it.

语言实现者可以使用一种称为尾调用优化，可以消除某些类的堆栈溢出。简而言之：如果函数的返回表达式只是函数调用的结果，那么您无需在堆栈中添加新级别，则可以将当前级别重用于所调用的函数。遗憾的是，几乎没有命令式语言实现内置了尾调用优化。

There is a technique that language implementers can use called tail call optimization which can eliminate some classes of stack overflow. Put succinctly: if a function's return expression is simply the result of a function call, then you don't need to add a new level onto the stack, you can reuse the current one for the function being called. Regrettably, few imperative language-implementations have tail-call optimization built in.

* 我喜欢递归。 我最喜欢的静态语言根本不使用循环，递归是重复做某件事的唯一方法。我只是不认为在不适合使用递归的语言中，递归通常不是一个好主意。

* I love recursion. My favorite static language doesn't use loops at all, recursion is the only way to do something repeatedly. I just don't think that recursion is generally a good idea in languages that aren't tuned for it.

**顺便提一下，Mario，您的ArrangeString函数的典型名称是 join，如果您选择的语言还没有实现它，我会感到惊讶。

** By the way Mario, the typical name for your ArrangeString function is "join", and I'd be surprised if your language of choice doesn't already have an implementation of it.

这篇关于什么是递归，什么时候应该使用它？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！