C中递归的内存和深度(vs.广度)

Question

我有两个与记忆相关的问题。首先是一些背景知识。我是一个初学者-中级c程序员。

我已经编写了几个不同的树状数据结构，每个级别都有不同数量的节点。一种这样的结构可以具有多个整数变量作为其数据，这些整数变量本身是整数树的主要数据。我已经为生成树编写了递归函数，这些树在不同的级别具有随机数量的节点。我将指向随机生成的整数树的指针作为生成主数据结构的参数传递。

我还编写了对这些树结构进行操作的递归代码，比如打印树。仅仅为了学习，我为我的节点创建了队列和堆栈，并编写了迭代函数来按顺序、预顺序和posr顺序打印树。我想，我开始掌握它的诀窍了。

现在的问题是。

(a)我需要编写其他函数，如果使用纯递归编写，这些函数显然是简单和干净的。我可以看到它是如何迭代编写的。这并不难，只是单调乏味。我的树的最大深度将是3-5，但是，每个级别的节点数量都很大。据我所知，每个递归调用都会将地址存储在堆栈中。如果深度很大，它可能会耗尽内存。但是如果深度很浅，使用递归函数的代价(内存/速度)可能并不可怕。

人们有没有关于决定迭代/递归解决方案是否更可取的标准的建议？我在这个网站上读到了关于迭代式soution的各种帖子，但找不到任何与这个问题直接相关的东西。

(b)第二，与向系统请求内存有关的问题。我知道有些应用程序可能会请求一定大小的内存。我在Netbeans IDE中使用mingw-gcc4.x。如何指定程序在调试/释放模式下可以使用的最大内存量？或者，它是否仅仅依赖于可用的RAM，而不需要明确的规范？！

提前谢谢你，

paras

~RT

Answer 1

“我的树的最大深度是3-5”

这种递归深度不会挑战任何Windows版本的默认堆栈大小，也不会挑战没有“小心！堆栈很小！”的任何其他系统的默认堆栈大小。涂得到处都是。大多数程序远不止3-5个调用深度，根本不涉及任何递归。

所以，只要你的递归只“下”你的树，而不是“跨越”它的广度，你就没问题。当然，除非你正在做一些非常不寻常的事情，比如在堆栈上粘贴一个巨大的数组作为局部变量。

你的(后序)递归看起来像这样，对吗？

void doNode(struct node *n) {
    for (int i = 0; i < n->num_nodes; ++i) {
        doNode(n->nodes[i]);
    }
    // do some work on this node
}

如果是这样，那么对于3-5个级别，它使用大量堆栈的唯一方式就是它看起来像这样：

void doNode(struct node *n) {
    int myRidiculousArray[100*1000] = { 0 };
    for (int i = 0; i < n->num_nodes; ++i) {
        doNode(n->nodes[i]);
    }
    // do some work on this node, using myRidiculousArray
}

如果您有数百万个节点，那么通过避免每个节点的函数调用开销，可能会有一些性能提升。但是先用简单的方式编写它，如果您迫切需要更高的性能，请稍后再回来查看它。每个节点的函数调用开销很少成为代码速度慢的原因--确实会发生这种情况，但通常只有在你修复了一系列其他甚至更糟糕的速度减慢之后才会发生。

Answer 2

如果您使用tail recursion编写函数(假设您在编译时启用了优化)，则不会遇到堆栈或内存空间的问题。

最后，您需要对您的函数进行编程，以便您能够理解它们，所以做任何对您来说更容易的事情。

Answer 3

(a)递归本身并不坏。然而，如果编写迭代算法的复杂度很接近，那么您应该使用迭代算法。在提交递归算法之前，需要满足一些前提条件：

-You应该确保递归深度(以及可重入函数中的局部变量)不会使您超出堆栈大小。对于你提到的在Windows上使用的深度，这在极少数情况下会是一个问题。此外，您还可以在树的高度上添加安全检查。

(b)如果您询问堆栈大小:我看到您使用mingw，因此您可能是为Windows构建的。Windows中的堆栈大小为每个线程。看看here如何设置保留的和初始提交的堆栈大小。

如果您正在询问有关堆内存分配的信息，请查看here。但简单地说，您可以使用系统为堆分配提供的所有内存。