blocks|key|1241146|text|递归函数主要用于设计算法。例如，您需要递归遍历目录树--它的深度是有限的，因此您很可能永远不会遇到太深的递归和随后的堆栈溢出，但是递归地编写树遍历要容易得多，然后以迭代的方式进行同样的操作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1241147|在大多数情况下，与迭代解决方案相比，递归函数不会节省内存。更糟糕的是，它们消耗的是堆栈内存，这相对来说是一种惊吓。|1241148|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Recursive functions are primarily used for ease of designing algorithms. For example you need to traverse a directory tree recursively - its depth it limited, so you're quite likely to never face anything like too deep recursion and consequent stack overflow, but writing a tree traversal recursively is soo much easier, then doing the same in iterative manner.

In most cases recursive functions don't save memory compared to iterative solutions. Even worse they consume stack memory which is relatively scarse.

blocks|key|1423468|text|它们有许多用途，没有它们，有些事情就很难实现。例如，迭代树。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1423469|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|$]]

they have many uses and some things become very difficult to impossible without them. iterating trees for instance.

blocks|key|1423507|text|在使用递归时，可以将数据存储在堆栈上(实际上，存储在当前实例之上所有函数的调用上下文中)，如果您试图使用while循环执行相同的操作，则可以使用动态分配将这些数据存储在堆中。想想大多数分而治之的算法，在每个调用上有两件事要做(也就是说，其中一个调用不是尾递归的)。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|1423508|关于Tom有趣的注释/子问题，递归函数的这种优势在C中可能特别明显，因为动态内存的管理是非常基本的。但这并不意味着它对C.|1423509|entityMap^0|1G|5|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|M|8|@]|D|@]|E|$]]|$1|H|3|-4|5|6|7|N|8|@]|D|@]|E|$]]]|I|$]]

When using recursion, you can store data on the stack (effectively, in the calling contexts of all the functions above the current instance) that you would have instead to store in the heap with dynamic allocation if you were trying to do the same thing with a <code>while</code> loop.
Think of most divide-and-conquer algorithms where there are two things to do on each call (that is, one of the calls is not tail-recursive).

And with respect to Tom's interesting comment/subquestion, this advantage of recursive functions is maybe particularly noticeable in C where the management of dynamic memory is so basic. But that doesn't make it very specific to C.

blocks|key|1423563|text|我认为使用递归有两个原因：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1423564|一种算法在递归数据结构上运行(例如树)|unordered-list-item|1423565|算法具有递归性质(通常发生在数学问题上，因为递归常常提供漂亮的解决方案)|1423566|小心处理递归，因为总是有无限递归的危险。|1423567|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$]]|$1|E|3|F|5|D|7|M|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|N|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|O|8|@]|9|@]|A|$]]]|J|$]]

There are two reasons I see for using recursion:

<ul>
<li>an algorithm operates on recursive data structures (like e.g. a tree)</li>
<li>an algorithm is of recursive nature (often happens for mathematical problems as recursion often offers beautiful solutions)</li>
</ul>

Handle recursion with care as there is always the danger of infinite recursion.

blocks|key|1241220|text|动态规划是递归至关重要的关键领域，尽管它超越了递归(记住子答案可以极大地提高性能)。算法是通常使用递归的地方，而不是典型的日常编码。与其说是编程概念，不如说是计算机科学概念。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1241221|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Dynamic_programming^0|0|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

<a href="http://en.wikipedia.org/wiki/Dynamic_programming" rel="nofollow noreferrer">Dynamic programming</a> is a key area where recursion is crucial, though it goes beyond that (remembering sub-answers can give drastic performance improvements). Algorithms are where recursion is normally used, rather than typical day to day coding. It's more a computer-science concept than a programming one.

blocks|key|2947013|text|递归函数使编写具有递推关系的解决方案变得更容易。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2947014|例如，阶乘函数有一个递归关系：|2947015|+factorial(0)+=+1
+factorial(n)+=+n+*+factorial(n-1)|code-block|syntax|javascript|2947016|下面我使用递归和循环实现了阶乘。|2947017|上面定义的递归版本和递归关系看起来很相似，因此更容易阅读。|2947018|递归：|2947019|double+factorial+(+int+n+)
{
+return+(+n+?+n+*+factorial+(+n-1+)+:+1+);
}|2947020|循环：|2947021|double+factorial+(+int+n+)
{
+double+result+=+1;
+while+(+n+>+1+)
+{
++result+=+result+*+n;
++n--;
+}
+return+result;
}|2947022|还有一件事：|2947023|阶乘的递归版本包括对自身的尾调用，并且可以对尾调用进行优化。这就使得递归阶乘的空间复杂度下降到迭代阶乘的空间复杂度。|2947024|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Recurrence_relation^0|9|4|0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|18|8|@]|9|@$A|19|B|1A|1|1B]]|C|$]]|$1|D|3|E|5|6|7|1C|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|1D|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|1E|8|@]|9|@]|C|$]]|$1|M|3|N|5|6|7|1F|8|@]|9|@]|C|$]]|$1|O|3|P|5|6|7|1G|8|@]|9|@]|C|$]]|$1|Q|3|R|5|H|7|1H|8|@]|9|@]|C|$I|J]]|$1|S|3|T|5|6|7|1I|8|@]|9|@]|C|$]]|$1|U|3|V|5|H|7|1J|8|@]|9|@]|C|$I|J]]|$1|W|3|X|5|6|7|1K|8|@]|9|@]|C|$]]|$1|Y|3|Z|5|6|7|1L|8|@]|9|@]|C|$]]|$1|10|3|-4|5|6|7|1M|8|@]|9|@]|C|$]]]|11|$12|$5|13|14|15|C|$16|17]]]]

Recursive functions make it easier to code solutions that have a <a href="http://en.wikipedia.org/wiki/Recurrence_relation" rel="nofollow noreferrer">recurrence relation</a>.

For instance the factorial function has a recurrence relation:

<pre><code> factorial(0) = 1
 factorial(n) = n * factorial(n-1)
</code></pre>

Below I have implemented factorial using recursion and looping.

The recursive version and recurrence relation defined above look similar and is
hence easier to read.

Recursive:

<pre><code>double factorial ( int n )
{
 return ( n ? n * factorial ( n-1 ) : 1 );
}
</code></pre>

Looping:

<pre><code>double factorial ( int n )
{
 double result = 1;
 while ( n &gt; 1 )
 {
 result = result * n;
 n--;
 }
 return result;
}
</code></pre>

One more thing:

The recursive version of factorial includes a tail call to itself and can be tail-call optimized. This brings the space complexity of recursive factorial down to the space complexity of the iterative factorial.

blocks|key|2947026|text|使用和不使用递归来实现QuickSort，然后您可以自己判断它是否有用。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2947027|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|$]]

Implement QuickSort with and without using recursion, then you can tell by yourself if it's useful or not.

blocks|key|1241253|text|递归在具有递归性质的问题上有一定的优势。其他的海报也提到了其中的一些。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1241254|利用C语言的递归能力，在内存管理方面具有一定的优势。当您试图避免递归时，大多数情况下使用自己的堆栈或其他动态数据类型来解决问题。这涉及到C/C%2B%2B中的动态内存管理。动态内存管理是昂贵和容易出错的！|1241255|您无法击败堆栈|offset|length|style|BOLD|1241256|另一方面，当您只使用堆栈并使用递归和局部变量时--内存管理非常简单，而且堆栈在大多数情况下比单独或普通C/C%2B%2B内存管理所能做的所有内存管理都更节省时间。这是因为系统栈是一种简单、方便、开销小的数据结构，它是使用专门的处理器操作来实现的。相信我，你无法战胜这一点，因为编译器、操作系统和处理器几十年来都是针对堆栈操作进行优化的！|1241257|PS:同样，堆栈不会像堆内存那样变得支离破碎。通过这种方式，还可以使用堆栈/递归来节省内存。|1241258|entityMap^0|0|0|0|7|0|0|0^^$0|@$1|2|3|4|5|6|7|P|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|Q|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|R|8|@$F|S|G|T|H|I]]|9|@]|A|$]]|$1|J|3|K|5|6|7|U|8|@]|9|@]|A|$]]|$1|L|3|M|5|6|7|V|8|@]|9|@]|A|$]]|$1|N|3|-4|5|6|7|W|8|@]|9|@]|A|$]]]|O|$]]

Recursion definitively has advantages at problems with a recursive nature. Other posters named some of them.

To use the capability of C for recursion definitively has advantages in memory management. When you try to avoid recursion, most of the time an own stack or other dynamic data type is used to break the problem. This involves dynamic memory management in C/C++. Dynamic memory management is costly and errorprone!

You can't beat the stack

On the other hand, when you just use the stack and use recursion with local variables -- the memory management is just simple and the stack is most of the time more time-efficient then all the memory management you can do by yourself or with plain C/C++ memory-management. The reason is that the system stack is such a simple and convenient data structure with low overhead and it is implemented using special processor operations that are optimized for this work. Believe me, you can't beat that, since compilers, operation systems and processors are optimized for stack manipulations for decades!

PS: Also the stack does not become fragmented, like heap memory does easily. This way it is also possible to save memory by using the stack / recursion.

blocks|key|1423713|text|我经常发现递归算法更容易理解，因为它们涉及较少的可变状态。考虑确定两个数的最大公因子的算法。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1423714|unsigned+greatest_common_divisor_iter(unsigned+x,+unsigned+y)
{
++++while+(y+!=+0)
++++{
++++++++unsigned+temp+=+x+%25+y;
++++++++x+=+y;
++++++++y+=+temp;
++++}
++++return+x;
}

unsigned+greatest_common_divisor(unsigned+x,+unsigned+y)
{
++++return+y+==+0+?+x+:+greatest_common_divisor(y,+x+%25+y);
}|code-block|syntax|javascript|1423715|在迭代版本中，有太多的重命名在进行，这符合我的口味。在递归版本中，一切都是不可变的，所以如果愿意，甚至可以制作x和y+const。|offset|length|style|CODE|1423716|entityMap^0|0|0|1N|5|0^^$0|@$1|2|3|4|5|6|7|O|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|Q|8|@$I|R|J|S|K|L]]|9|@]|A|$]]|$1|M|3|-4|5|6|7|T|8|@]|9|@]|A|$]]]|N|$]]

I often find recursive algorithms easier to understand because they involve less mutable state. Consider the algorithm for determining the greatest common divisor of two numbers.

<pre><code>unsigned greatest_common_divisor_iter(unsigned x, unsigned y)
{
 while (y != 0)
 {
 unsigned temp = x % y;
 x = y;
 y = temp;
 }
 return x;
}

unsigned greatest_common_divisor(unsigned x, unsigned y)
{
 return y == 0 ? x : greatest_common_divisor(y, x % y);
}
</code></pre>

There is too much renaming going on in the iterative version for my taste. In the recursive version, everything is immutable, so you could even make x and y <code>const</code> if you liked.

blocks|key|2947107|text|值得一提的是，在大多数函数语言(例如，Scheme)中，您可以利用尾调用优化，因此可以使用递归函数而不增加堆栈中的内存量。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2947108|基本上，复杂的递归尾调用可以在Scheme中完美地运行，而在C/C%2B%2B中，同样的调用会造成堆栈溢出。|2947109|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

One thing that is worth mentioning is that in most functional languages (Scheme for example), you can take advantage of tail call optimizations, and thus you can use recursive functions without increasing the amount of memory in your stack.

Basically, complex recursive tail calls can runs flawlessly in Scheme while in C/C++ the same ones will create a stack overflow.

If we consider recursive function in C/C++, are they useful in any way? Where exactly they are used mostly?
Are there any advantages in terms of memory by using recursive functions?

Edit: is the recursion better or using a while loop?

Recursive functions in C/C++

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

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

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

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

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

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

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

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

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

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

如果我们考虑C/C++中的递归函数，它们在任何方面都有用吗？它们究竟是在哪里使用的？使用递归函数在内存方面有什么优势吗？编辑:递归是更好还是使用Edit循环？

问C/C++中的递归函数
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C/C++中的递归函数EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问C/C++中的递归函数
EN