c - c中递归的内存和深度(与广度)

Question

我有两个与内存有关的问题。首先是一些背景。我是一名新手中级 c 程序员。

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

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

现在是问题。

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

人们对决定迭代/递归解决方案是否更可取的标准有建议吗？我已经阅读了网站上关于迭代解决方案的各种主题，但找不到任何直接说明这个问题的内容。

(b) 其次，问题与从系统请求内存有关。我知道某些应用程序可以请求一定数量的内存。我在 Netbeans IDE 中使用 mingw-gcc4.x。如何指定程序在调试/ Release模式下可以使用的最大内存量？或者，它是否仅取决于可用的 RAM 而无需明确指定？!

提前致谢

段落

~回复

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
}

如果您有数百万个节点，那么避免每个节点的函数调用开销可能会带来一些性能提升。但是先以简单的方式编写它，然后如果您迫切希望获得更高的性能，稍后再回来查看它。每个节点的函数调用开销很少会成为您的代码缓慢的原因 - 它确实会发生，但通常只有在您修复了一堆其他甚至更糟糕的减速之后。