blocks|key|4998333|text|在大多数情况下，递归速度较慢，并且会占用更多的堆栈。递归的主要优点是，对于像树遍历这样的问题，它使算法变得更容易或更“优雅”。看看下面的一些比较：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4998334|link|offset|length|4998335|entityMap|0|LINK|mutability|MUTABLE|url|http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html#iter^0|0|0|4|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@$D|P|E|Q|1|R]]|A|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|A|$]]]|G|$H|$5|I|J|K|A|$L|M]]]]

For the most part recursion is slower, and takes up more of the stack as well. The main advantage of recursion is that for problems like tree traversal it make the algorithm a little easier or more "elegant".
Check out some of the comparisons:

<a href="http://pages.cs.wisc.edu/~vernon/cs367/notes/6.RECURSION.html#iter" rel="noreferrer">link</a>

blocks|key|3397981|text|递归意味着一个函数重复调用|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3397982|它使用系统堆栈来完成其任务。由于堆栈使用后进先出方法，并且当调用一个函数时，受控对象被移动到定义函数的位置，该函数以某个地址存储在内存中，该地址被存储在堆栈中|3397983|其次，它降低了程序的时间复杂度。|3397984|虽然有点离题，但有点相关。必读。：Recursion+vs+Iteration|offset|length|3397985|entityMap|0|LINK|mutability|MUTABLE|url|http://benpfaff.org/writings/clc/recursion-vs-iteration.html^0|0|0|0|H|M|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|T|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|U|8|@]|9|@$H|V|I|W|1|X]]|A|$]]|$1|J|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|Q]]]]

Recursion means a function calls repeatedly

It uses system stack to accomplish it's task. As stack uses LIFO approach
and when a function is called the controlled is moved to where function is defined which has it is stored in memory with some address, this address is stored in stack

Secondly, it reduces a time complexity of a program. 

Though bit off-topic,a bit related. Must read. : <a href="http://benpfaff.org/writings/clc/recursion-vs-iteration.html" rel="noreferrer">Recursion vs Iteration</a>

blocks|key|2015696|text|所有的算法都可以递归定义。这使得可视化和证明它变得更加容易。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2015697|有些算法(例如Ackermann+Function)不能(很容易)迭代地指定。|offset|length|2015698|如果不能执行tail+call+optimization，那么递归实现将比循环使用更多的内存。虽然迭代可能比无法优化的递归函数使用更少的内存，但它的表达能力有一些限制。|2015699|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Ackermann_function|1|http://en.wikipedia.org/wiki/Tail_call^0|0|7|I|0|0|6|M|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@$D|X|E|Y|1|Z]]|A|$]]|$1|H|3|-4|5|6|7|10|8|@]|9|@]|A|$]]]|I|$J|$5|K|L|M|A|$N|O]]|P|$5|K|L|M|A|$N|Q]]]]

All algorithms can be defined recursively. That makes it much, much easier to visualize and prove. 

Some algorithms (e.g., the <a href="http://en.wikipedia.org/wiki/Ackermann_function" rel="noreferrer">Ackermann Function</a>) cannot (easily) be specified iteratively. 

A recursive implementation will use more memory than a loop if <a href="http://en.wikipedia.org/wiki/Tail_call" rel="noreferrer">tail call optimization</a> can't be performed. While iteration may use less memory than a recursive function that can't be optimized, it has some limitations in its expressive power.

blocks|key|1331131|text|任何使用递归实现的算法也可以使用迭代实现。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1331132|为什么不使用递归|1331133|1331134|由于维护堆栈的开销，它通常较慢。|ordered-list-item|1331135|它通常为堆栈使用更多内存。|1331136|1331137|为什么要使用递归|1331138|+time递归增加了清晰度，并(有时)减少了编写和调试代码所需的时间(但不一定会减少execution).|1331139|Reduces+time+complexity.|1331140|Performs的空间需求或速度)更好地解决基于树结构的问题。|1331141|1331142|例如，与迭代相比，使用递归更容易解决汉诺塔问题。|1331143|entityMap^0|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|X|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Y|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|10|8|@]|9|@]|A|$]]|$1|H|3|I|5|G|7|11|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|12|8|@]|9|@]|A|$]]|$1|K|3|L|5|6|7|13|8|@]|9|@]|A|$]]|$1|M|3|N|5|6|7|14|8|@]|9|@]|A|$]]|$1|O|3|P|5|G|7|15|8|@]|9|@]|A|$]]|$1|Q|3|R|5|G|7|16|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|17|8|@]|9|@]|A|$]]|$1|T|3|U|5|6|7|18|8|@]|9|@]|A|$]]|$1|V|3|-4|5|6|7|19|8|@]|9|@]|A|$]]]|W|$]]

Any algorithm implemented using recursion can also be implemented using iteration.

<h2>Why not to use recursion</h2>

<ol>
<li>It is usually slower due to the overhead of maintaining the stack.</li>
<li>It usually uses more memory for the stack.</li>
</ol>

<h2>Why to use recursion</h2>

<ol>
<li>Recursion adds clarity and (sometimes) reduces the time needed to write and debug code (but doesn't necessarily reduce space requirements or speed of execution).</li>
<li>Reduces time complexity.</li>
<li>Performs better in solving problems based on tree structures.</li>
</ol>

For example, the Tower of Hanoi problem is more easily solved using recursion as opposed to iteration.

blocks|key|1330970|text|我个人更喜欢使用迭代而不是递归函数。特别是当你的函数有复杂/繁重的逻辑，并且迭代次数很大的时候。这是因为随着每个递归调用堆栈的增加。如果你的操作太大，它可能会使堆栈崩溃，还会减慢进程。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1330971|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I personally prefer using Iterative over recursive function. Especially if you function has complex/heavy logic and number of iterations are large. This because with every recursive call call stack increases. It could potentially crash the stack if you operations are too large and also slow up process.

blocks|key|1331060|text|要开始：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1331061|优点：|1331062|1331063|它是实现可变数量的嵌套循环的唯一方法(也是实现大量恒定数量的嵌套循环的唯一优雅方法)。|unordered-list-item|1331064|1331065|缺点：|1331066|1331067|递归方法在处理大集时通常会抛出StackOverflowException。但是递归循环没有这个问题。|1331068|1331069|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|R|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|S|8|@]|9|@]|A|$]]|$1|E|3|F|5|G|7|T|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|W|8|@]|9|@]|A|$]]|$1|L|3|M|5|G|7|X|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]|$1|O|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|P|$]]

To start:

Pros:

<ul>
<li>It is the unique way of implementing a variable number of nested loops (and the only elegant way of implementing a big constant number of nested loops).</li>
</ul>

Cons:

<ul>
<li>Recursive methods will often throw a StackOverflowException when processing big sets. Recursive loops don't have this problem though.</li>
</ul>

blocks|key|1331179|text|表现力|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1331180|大多数问题都自然地用递归表示，如斐波那契、归并排序和快速排序。在这方面，代码是为人类编写的，而不是机器。|1331181|不变性|1331182|迭代解决方案通常依赖于不同的临时变量，这使得代码难以阅读。这可以通过递归来避免。|1331183|性能|1331184|递归不是堆栈友好的。当递归设计得不好或不支持尾部优化时，堆栈可能会溢出。|1331185|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|P|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Q|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|R|8|@]|9|@]|A|$]]|$1|J|3|K|5|6|7|S|8|@]|9|@]|A|$]]|$1|L|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|M|$]]

<h2>Expressiveness</h2>

Most problems are naturally expressed by recursion such as Fibonacci, Merge sorting and quick sorting. In this respect, the code is written for humans, not machines. 

<h2>Immutability</h2>

Iterative solutions often rely on varying temporary variables which makes the code hard to read. This can be avoided with recursion.

<h2>Performance</h2>

Recursion is not stack friendly. Stack can overflow when the recursion is not well designed or tail optimization is not supported.

blocks|key|3398137|text|在某些情况下，您将不得不在递归似乎对您有利问题中放弃递归，这是因为对于您的递归必须发生数千次的问题，这将导致堆栈溢出错误，即使您的代码没有陷入无限递归。大多数编程语言都会限制堆栈调用的次数，所以如果递归超过了这个限制，那么可以考虑不使用递归。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3398138|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Some situation would arise where you would have to abandon recursion in a problem where recursion appears to be to your advantage, this is because for problems where your recursion would have to occur thousand of times this would result in a stackoverflow error even though your code did not get stuck in an infinite recursion. Most programming languages limits you to a number of stack calls, so if your recursion goes beyond this limit, then you might consider not using recursion.

blocks|key|3398157|text|我们应该在以下场景中使用递归：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3398158|当我们不知道有限的迭代次数时，例如，我们的函数退出条件是基于动态规划的，我们需要对元素的逆序进行操作。，，(memoization)|3398159|when，，|unordered-list-item|3398160|。这意味着我们希望首先处理最后一个元素，然后是n-1、n-2，依此类推，直到第一个元素|3398161|为止|3398162|3398163|递归将保存多次遍历。如果我们可以像这样划分堆栈分配，那么它将是有用的：|3398164|int+N+=+10;
int+output+=+process(N)+%2B+process(N/2);
public+void+process(int+n)+{
++++if+(n==N/2+%2B+1+%7C%7C+n==1)+{
+++++++return+1;
++++}

++++return+process(n-1)+%2B+process(n-2);
}|code-block|syntax|javascript|3398165|在这种情况下，在任何给定时间都只分配一半堆栈。|3398166|entityMap^0|0|0|1|1|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$]]|$1|G|3|H|5|F|7|Z|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|10|8|@]|9|@]|A|$]]|$1|K|3|-4|5|6|7|11|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|12|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|13|8|@]|9|@]|A|$Q|R]]|$1|S|3|T|5|6|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

We should use recursion in following scenarios:

<ul>
<li>when we don't know the finite number of iteration for example our fuction exit condition is based on dynamic programming (memoization)</li>
<li>when we need to perform operations on reverse order of the elements. Meaning we want to process last element first and then n-1, n-2 and so on till first element</li>
</ul>

Recursion will save multiple traversals. And it will be useful, if we can divide the stack allocation like:

<pre><code>int N = 10;
int output = process(N) + process(N/2);
public void process(int n) {
 if (n==N/2 + 1 || n==1) {
 return 1;
 }

 return process(n-1) + process(n-2);
}
</code></pre>

In this case only half stacks will be allocated at any given time.

blocks|key|1331299|text|递归得到了一个糟糕的名声，我总是惊讶于许多开发人员甚至不会接触到递归，因为有人告诉他们它是邪恶的化身。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1331300|我通过试验和错误了解到，当正确地处理递归时，它可以是迭代某些东西的最快方法之一，它不是一个固定的规则，并且每种语言/编译器/引擎都有它自己的怪癖，所以里程会有所不同。|1331301|在javascript中，我可以通过引入递归来可靠地加速几乎任何迭代过程，同时还可以减少副作用，使代码更加清晰、简洁和可重用。此外，pro提示可以绕过堆栈溢出问题(不，您不禁用该警告)。|1331302|我个人的优点和缺点：|1331303|优点：|1331304|-+Reduces+side+effects.
-+Makes+code+more+concise+and+easier+to+reason+about.
-+Reduces+system+resource+usage+and+performs+better+than+the+traditional+for+loop.|code-block|syntax|javascript|1331305|缺点：|1331306|-+Can+lead+to+stack+overflow.
-+More+complicated+to+setup+than+a+traditional+for+loop.|1331307|里程数将根据语言/编译器/引擎的不同而不同。|1331308|entityMap^0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|Y|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|Z|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|10|8|@]|9|@]|A|$]]|$1|J|3|K|5|L|7|11|8|@]|9|@]|A|$M|N]]|$1|O|3|P|5|6|7|12|8|@]|9|@]|A|$]]|$1|Q|3|R|5|L|7|13|8|@]|9|@]|A|$M|N]]|$1|S|3|T|5|6|7|14|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|15|8|@]|9|@]|A|$]]]|V|$]]

Recursion gets a bad rep, I'm always surprised by the number of developers that wont even touch recursion because someone told them it was evil incarnate.
I've learned through trial and error that when done properly recursion can be one of the fastest ways to iterate over something, it is not a steadfast rule and each language/ compiler/ engine has it's own quirks so mileage will vary.
In javascript I can reliably speed up almost any iterative process by introducing recursion with the added benefit of reducing side effects and making the code more clear concise and reusable. Also pro tip its possible to get around the stack overflow issue (and no you dont disable the warning).
My personal Pros &amp; Cons:
Pros:
<pre><code>- Reduces side effects.
- Makes code more concise and easier to reason about.
- Reduces system resource usage and performs better than the traditional for loop.
</code></pre>
Cons:
<pre><code>- Can lead to stack overflow.
- More complicated to setup than a traditional for loop.
</code></pre>
Mileage will vary depending on language/ complier/ engine.

With respect to using recursion over non-recursive methods in sorting algorithms or, for that matter, any algorithm what are its pros and cons?

What are the advantages and disadvantages of recursion?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

关于在排序算法或任何算法中使用递归而不是非递归方法，它的优缺点是什么？

问递归的优点和缺点是什么？
EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问递归的优点和缺点是什么？EN

回答 10

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问递归的优点和缺点是什么？
EN