recursion - 500次递归调用是不是太多了？

Question

Codility 任务之一是查找二叉树的高度。该任务保证高度不会超过 500。因此想到的最简单的解决方案就是使用递归。

现在，虽然这样的解决方案通过了 Codility 中的所有测试，但我想知道我是否可以安全地假设 500 并不算太多(对于任何计算机/测试平台这可能是 Codility 的测试平台)或我是否应该避免递归并模拟它或以其他方式找到树的高度？

编辑: 正如 PM 77-1 指出的那样，答案可能取决于我的递归是什么样子。所以我把它包括在内。定义了一个struct:

struct tree {
  int x;
  tree * l;
  tree * r;
}; 

这是我的解决方案:

int getHeight(tree const * T, int height)
{
    int maxHeight = height;
    if (T->l)
    {
        maxHeight = getHeight(T->l, height + 1);
    }
    if (T->r)
    {
        maxHeight = max(maxHeight, getHeight(T->r, height + 1));
    }
    return maxHeight;
}

int solution(tree * T)
{
    return getHeight(T, 0);
}

现在我的问题是 - 知道我的解决方案是什么样子(它可以使用多少内存/等等...)并且不知道测试平台规范是什么，我可以安全地假设 500 次递归调用不会导致是否存在堆栈溢出？(因为如果是 50 或 5，我想我可以放心地假设，无论测试平台如何。)

编辑:我故意没有指定语言，因为 Codility 支持多种语言，如果可能的话，我希望获得有关多种语言的答案。不过，我在解决方案中使用了 C++，所以我想这是我最感兴趣的语言。

Answer 1

这取决于许多因素，包括语言和方法每次调用使用的堆栈空间量。

对于 Java，引用类型为 8 个字节，默认堆栈大小通常为 512 kB。一个方法至少需要 1 个引用(8 个字节)来存储返回地址，加上您声明的任何变量和参数(也可能每个都是 8 个字节，因为您将使用的 Java 中的大多数变量将是引用或 8 字节整数)。

让我们计算每次调用有多少堆栈空间可用。请注意，此计算忽略了程序其余部分所需的空间，并假设递归方法是堆栈中的唯一方法。我们还将假设该方法不调用除自身之外的方法，因为很难说它们需要多少堆栈。事实上，您的工作空间会稍微少一些。

(512000 bytes) / (500 calls) = 1024 bytes per call
(1024 bytes per call) / (8 bytes per reference) = 128 references per call

因此，对于 500 级递归，在用完堆栈空间之前，您的方法中可以有 127 个变量和参数(因为我们已为返回地址减去 1)。即使有这些假设，您似乎也不太可能达到此限制。