在大多数情况下，递归函数使用的内存是 C 中迭代函数的两倍吗？

Question

 // Recursive Implementation:
int factorialResult(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return factorialResult(n - 1) * n;
    }
}



// Iterative Implementation:
int factorialResult(int n) {
    int factorialSum = 1;
    for (int i = 1; i <= n; i++) {
        factorialSum *= i;
    }

    return factorialSum;
}

在 C 中的大多数情况下，递归函数实现是否会使用更多内存？如果是这样，它的内存是否是相应迭代函数实现的两倍？

Answer 1

所有这些内存都是堆栈内存。与堆内存相比，堆栈内存的分配成本较低。堆栈分配需要 O(1) 时间 - 它只是移动堆栈指针。

但它是有限的。线程在高端计算机上通常具有 1MB 的堆栈，在低端设备上则具有约 100KB。取决于编译器设置和操作系统架构。因此，如果您调用递归

factorial(500000)

，那么在溢出结果返回给调用者之前，它就会遇到字面上的“堆栈溢出”错误。