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

Question

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.

Take note that recursion CAN run in constant time IF the procedure uses tail-recursion AND if the language supports tail-call optimization. Look up "tail-recursion" if you're interested. — erjiang, Nov 02 '10 at 18:39
Also, on some CPUs like the Sparc function call overhead is very low. And with some programming lanuages like Tcl, function call is actually faster than inline code (due to how the bytecompiler works). — slebetman, Nov 02 '10 at 23:08

score 3 · Accepted Answer · answered Nov 02 '10 at 18:25

3

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.

answered Nov 02 '10 at 18:25

codymanix

28,510
21
92
151

1

thats what I thought, but why would that be unpredictable? – Lazer Nov 02 '10 at 18:27
3

I think it just means "depends on a value at runtime". The iterative version I can predict always takes 8 bytes of stack (or whatever it takes), whereas I cannot "predict" the recursive one, since it depends on the value of `number` passed in at runtime. So "unpredictable" means "unable to predict a constant value at compile-time". – Brian Nov 02 '10 at 18:30
It would be un predictable if you wouldn't know how many times the function calls itself, right? If the function calls itself too many times you would have a `stackoverflow` =) – gideon Nov 02 '10 at 18:31
1

@Lazer: That depends on your algorithm. If you've got a limit on how many times your function will call itself, then you can predict memory use. If not, then it's unpredictable. In the factorial example, your function calls itself n - 1 times to calculate n!, so there's no real limit. (Of course, the size of n such that n! can be expressed as a `int` is not that large, and if n is larger we get undefined behavior anyway.) – David Thornley Nov 02 '10 at 18:32
@gideon will increasing the stack reserve size or stack commit size help ? – sameer karjatkar Jan 11 '13 at 12:06

score 1 · Answer 2 · edited May 23 '17 at 12:19

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?

score 0 · Answer 3 · answered Nov 02 '10 at 18:36

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.

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

3 Answers3