在C语言中，多数情况下递归函数内存占用是否高于迭代实现？若如此是否约为两倍？

代码实现 #

递归实现 #

// 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语言多数场景下，递归实现的内存占用确实比迭代实现更高。
  原因是递归调用时，每一次函数调用都会在程序栈内存中创建新的栈帧，用来保存当前函数的参数、返回地址以及局部变量。计算n!的递归实现需要连续调用n次函数，栈上会同时存在n个栈帧，内存占用随递归深度线性增长（复杂度为O(n)）。
• 递归的内存占用绝非迭代的两倍。迭代实现仅需一个栈帧，里面仅存放少量局部变量（factorialSum和循环变量i），内存占用是固定的常量级（复杂度为O(1)）。递归的内存占用取决于递归深度n，当n较大时，递归的内存占用会远高于迭代，二者差距根本不是固定的两倍关系。

内容的提问来源于stack exchange，提问作者Software Guy