algorithm - 如何评估堆栈溢出前的最大递归调用次数

Question

让我们采用递归函数，例如阶乘。我们还假设我们有一个 1 MB 大小的堆栈。使用笔和纸，我如何估计在堆栈溢出之前对函数的递归调用次数？我对任何特定语言都不感兴趣，而是对抽象方法感兴趣。

关于 SO 的问题看起来很相似，但大多数问题都与特定语言有关，或者扩展堆栈大小，或者通过运行特定函数来估计它，或者防止溢出。我想找到一种数学方法来估计它。

我在算法挑战中发现了类似的问题，但无法提出任何合理的解决方案。

非常感谢任何建议。

编辑

作为对提供的重播的回应，如果语言真的不能被排除在等式之外，我们假设它是 C#。此外，由于我们将简单的 int 或 long 传递给函数，因此它不是通过引用传递的，而是作为副本传递的。此外，假设一个简单的实现，没有散列，没有多线程，一个尽可能类似于函数的数学表示的实现:

    private static long Factorial(long n)
    {
        if (n < 0)
        {
            throw new ArgumentException("Negative numbers not supported");
        }

        switch (n)
        {
            case 0:
                return 1;
            case 1:
                return 1;
            default:
                return n * Factorial(n - 1);
        }
    }

Answer 1

这在很大程度上取决于功能的实现。在再次调用自身之前，该函数使用了多少内存。当它递归 100 次时，内存中也会有 100 个函数作用域，包括函数参数和变量。它还在堆栈上预留了 100 个位置来存储返回值。

我不认为语言可以轻易地排除在等式之外，因为您需要确切地知道堆栈是如何使用的。例如，对象是通过引用传递的吗？或者对象是否作为堆栈上的新实例复制？