Do recursive functions use twice as much memory as their iterative counterparts in C, in most cases?

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;
}

In most cases in C, do recursive function implementations use more memory? And if so, is it around double the memory of a corresponding iterative function implementation?

Answer 1

Not "twice as much" memory, but on the order of n times as much memory is likely used.

All of this memory is stack memory. Stack memory is cheap to allocate compared to heap memory. A stack allocation takes O(1) time - it just moves the stack pointer.

But it's limited. Threads usually have a megabyte of stack on high-end computers to about 100KB on low-end devices. Depends on compiler settings and OS architecture. So if you invoked the recursive factorial(500000), it would hit a literal "stack overflow" error long before the overflowed result could be returned to the caller.

Answer 2

In your factorial implementations, no heap memory space is used, so in that respect, the two are identical. Where they may differ is in stack space usage.

The recursive solution is O(n) in stack space usage, while the iterative solution uses constant stack space. Given enough recursive calls, the recursive solution may yield a stack overflow error.

There are a few provisos here:

1. Your compiler may implement tail-call optimization, where if the last (or "tail") call in your function is simply another function call, the compiler may be able to convert it to a simple loop.

E.g.

int factorialResult_tailRec(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    else {
        return factorialResult_tailRec(n - 1, acc * n);
    }
}

Where this is called as factorialResult_tailRec(5, 1).

However, this optimization should not be counted upon.

2. Consider carefully your data types. You may overflow int before you ever encounter a stack overflow. For instance, 13! already overflows a 32-bit int, but those recursive calls will have no substantial effect on stack space. Even if you expand your data to a 64-bit integer, 21! still overflows and has no significant effect on stack space.