How does recursion make the use of run-time memory unpredictable?

Question

Quoting from Code Complete 2,

int Factorial( int number ) {
   if ( number == 1 ) {
      return 1;
   }
   else {
      return number * Factorial( number - 1 );
   }
}

In addition to being slow ^[1] and making the use of run-time memory unpredictable ^[2], the recursive version of this routine is harder to understand than the iterative version, which follows:

int Factorial( int number ) {
   int intermediateResult = 1;
   for ( int factor = 2; factor <= number; factor++ ) {
      intermediateResult = intermediateResult * factor;
   }
   return intermediateResult;
}

I think the slow part is because of the unnecessary function call overheads.

But how does recursion make the use of run-time memory unpredictable?

Can't we always predict how much memory would be needed (as we know when the recursion is supposed to end)? I think it would be as unpredictable as the iterative case, but not any more.

Answer 1

Because of the fact recursive methods call them selves repeatedly, the need lots of stack memory. Since the stack is limited, errors will occur if the stack memoy is exceeded.

Answer 2

Can't we always predict how much memory would be needed (as we know when the recursion is supposed to end)? I think it would be as unpredictable as the iterative case, but not any more.

No, not in the general case. See discussion about the halting problem for more background. Now, here's a recursive version of one of the problems posted there:

void u(int x) {
    if (x != 1) {
        u((x % 2 == 0) ? x/2 : 3*x+1);
    }
}

It's even tail-recursive. Since you can't predict if this will even terminate normally, how can you predict how much memory is needed?

Answer 3

If the recursion level becomes too deep, you'll blow the call stack and eat up lots of memory in the process. This can happen if your number is a "large enough" value. Can you do worse than this? Yes, if your function allocates more objects with every recursion call.