stack-overflow in recursions in Racket

Question

Recursions are highly promoted in Racket as part of functional programming. However, stack overflow is an important problem generally mentioned with recursion. Are there any situations in Racket where stack overflow can occur and what precautions should one take to prevent such occurrences?

Answer 1

I think it is slightly confusing to talk about stack overflow, because it may be that the implementation doesn't actually use a stack, or stores the stack on the heap or something else (and I think Racket does at least one if not both of these).

More useful is to ask how the storage required by a computation changes for different values of the arguments to that computation. Naïvely, it looks as though, if you specify a computation recursively, the storage does grow, at least as fast as the depth of the recursion.

But in fact it doesn't have to. Consider a function like this:

(define (complicated n)
  (let ((y (f n)))
    ...
    (g y)))

And in particular consider the calls to f and g:

• when f is called then the system needs to remember to itself that it needs to return to complicated to do more work.
• but when g is called, it doesn't: the call to g is the very last thing that complicated does, and its return value is just immediately returned from complicated (note it doesn't matter that y is bound at this point: when g is called that binding can never be referenced again).

Well, a long time ago people started to write Lisp implementations which made use of this, and optimised such 'tail' calls away, thus enabling a much nicer approach to programming where you didn't have to turn things into loops all the time, because the system would do it for you.

A good (and very traditional) example is functions which are a bit like the factorial function: things which are naturally recursively defined. Rather than factorial (which typically creates enormous numbers which are a pain to print) consider the function s, defined as:

• s(0) = 0;
• s(n) = n + s(n - 1)

(this is very like factorial, of course).

In a traditional, non-tail-call-optimising Lisp you would have to turn this into a loop if you want to calculate it for large values of n (this example is Common Lisp):

(defun s (n)
  (let ((sum n))
    (dotimes (i n sum)
      (incf sum i))))

But in a system which optimises tail calls, you might be tempted to try and write it recursively: just following the definition.

(define (s n)
  (if (= n 0)
      n
      (+ n (s (- n 1)))))

And now you get a nasty surprise: it runs out of storage (on my Racket, it dies for arguments somewhere between 1000 and 1000000, I haven't checked where exactly). Well, it's easy to see why it runs out of storage: the call to s is not a tail call, because after it returns the result still needs to have n added to it. So it's a real recursive call, and it requires storage.

But you can turn the thing into a tail call by considering an alternative definition of s:

• s(n) = l(n, 0)
• l(0, a) = a
• l(m, a) = l(m - 1, a + m)

And you can turn this into code:

(define (s n)
  (define (l m a)
    (if (= m 0)
        a
        (l (- m 1) (+ a m))))
  (l n 0))

It's easy to see that all the calls to l are now tail calls, and indeed this version of s is completely happy for much larger values of its argument (it eventually starts consing a lot of bignums and gets rather slow as a result, but it will run without exhausting storage).

This is all very well, except that I haven't defined when a call is a tail call: I've said 'it's obvious that' and things like that, but I haven't sat down and written a specification. And if I want tail calls to be eliminated as part of the language rather than as a compiler optimisation which may or may not happen, then I had better do that.

Well, that's what Scheme (and, following Scheme, Racket) did: the language itself specifies which calls are tail calls, and says that such calls don't use storage. How it does that turns out to involve hairy questions of language semantics which I (as an old-fashioned Lisp hacker) don't really understand: a starting point is perhaps here.

Answer 2

No. You will never get a stack overflow in Racket. This is because the Racket VM doesn't really store memory in the OS level call stack. What you can do, however, is use up all of your machines memory. You do this by using functions that requires the Racket VM to continually store more and more space. For example:

(define (f)
  (define x (random))
  (f)
  x)

In this function, Racket will need to store an unbounded number of random x values before it can start returning, which will cause your VM to run out of memory.

On the other hand if you swap two lines in the function:

(define (f)
  (f)
  (define x (random))
  x)

Your function will still never terminate, and will also take significantly longer to run out of memory. This is because the VM only needs to remember to return to a previous call to f before it finishes, but it does not need to store space for x.

Finally, if we have this function:

(define (f)
  (define x (random))
  x
  (f))

The function will never terminate, but it will also never run out of memory. This is because it allocates a space for x, but is able to drop that space when it recursively calls f. Also, because the recursive call is the last thing that the function does, it also no longer needs to store the original call to f, meaning that no new space is needed for each recursive function call. This is called tail call elimination.¹ In effect, this last function is equivalent to an infinite loop in C or Java.

_{¹Note that some people incorrectly call this tail call optimization. This is not an optimization as it is part of the core semantics of the language. Calling it an 'optimization' would be just as wrong as calling Java's GC an 'optimization'.}

Answer 3

Stack overflows are most often a problem with bad recursion, or what is often called infinite recursion. So first you want to address that.

Second, if your recursion is written in such a way that there is nothing to do after any recursive call other than return, you have what is known as tail recursion, which can be optimized by the interpreter/compiler to re-use the current stack frame, and thus eliminate the possibility of stack overflow (at least from that cause). This is not always possible, but can be a big win if employed.

For example:

• This would produce a stack overflow:

  (define (f n) 
      (+ 1 (f (- n 1)))
  

• This wouldn't, but would never terminate, either:

  (define (f n) 
      (f n))
  

• And this would have neither problem:

  (define (f n) 
      (if (<= n 0) 
          n 
          (f (- n 1))))