Recursion and StackOverflowError

Question

How would you adjust this simple recursion example so that tail call optimization occurs (and not a StackOverflowError)?

count 0 = 0
count n = succ (count (pred n))
count 100000

Answer 1

This is the kind of stack overflows I call the "length/foldr" kind. It occurs, when the recursive function is applied to compute the strict argument of the function application that constitutes the result. Compare:

-- naive computation of list length
-- this is not like it's defined in Frege, of course
length [] = 0
length (_:xs) = 1 + length xs

This also happens with foldr f when f is strict in its second argument.

There are other possible reasons for stack overflows (SO):

1. tail recursion. This is handled in Frege most efficiently, because a tail recursive function is compiled to a while loop. Will never actually cause a SO, unlike in other JVM languages.
2. explicit indirect tail recursion: (e.g. a tail calls b, which tail calls c, ..., which tail calls a). This should also never result in a SO in Frege.
3. building of thunks that are so deeply nested that SO occurs on evaluation. This is what happens in foldl in Haskell. In Frege, the standard fold is strict in the accumulator and hence immune in many cases. However, the following still overflows on long lists: fold (<>) mempty (map (Just . Sum) [1..10000])
4. The length/foldr kind of recursion, as in our example.
5. Recursion in non tail calls:

Here is an example for the last case:

  even 0 = true
  even n = case even (pred n) of
           true  -> false
           false -> true

The second equation is semantically equivalent to even n = not (even (pred n)) and thus is an even more malicious variant of 4.

To answer your question, in your example one could use an accumulator to create a tail-recursive version:

count n = go 0 n
    where
       go acc 0 = acc
       go acc n = go (succ acc) (pred n)

It is perhaps worth noting that your example also fails in Haskell:

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer-gmp ... linking ... done.
Loading package base ... linking ... done.
Prelude> let count 0 = 0; count n = succ (count (pred n))
Prelude> count 10000
10000
Prelude> count 100000
100000
Prelude> count 1000000
1000000
Prelude> count 10000000
10000000
Prelude> count 100000000
*** Exception: stack overflow

The reason that it overflows only with much higher numbers is that the Haskell RTS manages the RAM in a way that is better suited for functional programming, whereas the JVM allocates a tiny default stack on startup, that accommodates a call depth of a few 1000 at best.

You can compute much greater numbers with your program even in Frege when you force the JVM to allocate bigger stacks:

java -Xss512m ....

Experience shows that a stack of size 512m allows a call depth of approximatly 10 million for single argument functions.

This is, however, not a general solution, because then the JVM creates all threads with this stack size. Thus precious RAM is wasted. And even when you have plenty of RAM, you'll probably not be able to create a stack greater than 2g.

In the next major version of Frege, certain pathological cases of stack overflow kinds 3 and 4 (see above) will be managed better, hopefully. As of today, however, such constructs will work only for small problem sizes that happen to fit the JVM stack.