Are programs in functional languages more likely to have stack overflows?

Question

I am starting to learn ocaml, and am really appreciating the power of recursion in the language. However, one thing that I am worried about is stack overflows.

If ocaml uses the stack for function calls, won't it eventually overflow the stack? For example, if I have the following function:

let rec sum x =
  if x > 1 then f(x - 1) + x
  else x;;

it must eventually cause a stack-overflow. If I was to do the equivalent thing in c++ (using recursion), I know that it would overflow.

So my question is, is there built in safeguards to prevent functional languages from overflowing the stack? If not, are they not less useful like this, since the above summing algorithm, written in a procedural style with a for loop, could handle any number (dis-regarding integer overflow)?

Answer 1

All (decent implementations of;-) functional languages optimize tail recursion, but that's not what you're doing here, since the recursive call is not the LAST operation (it needs to be followed by the addition).

So, one soon learns to use an auxiliary function that IS tail recursive (and takes the current total being accumulated as an argument) so the optimizer can do its job, i.e., net of possible O'Caml syntax in which I'm rusty:

let sum x =
  aux(x)(0);;

let rec aux x accum =
  if x > 1 then aux(x - 1)(accum + x)
  else (accum + x);;

Here, the sum happens as an ARGUMENT to the recursive call, i.e., BEFORE the recursion itself, and so tail optimization can kick in (because the recursion IS the last thing that needs to happen!).

Answer 2

Functional languages typically have a MUCH larger stack. For example, I've written a function specifically to test stack limits in OCaml, and it got to over 10,000 calls before it barfed. However, your point is valid. Stack-overflows are still something you need to watch out for in functional languages.

One of the strategies that functional languages use to mitigate their reliance on recursion is the use of tail-call optimization. If the call to the next recursion of the current function is the last statement in the function, the current call can be discarded from the stack and the new call instantiated in its place. The assembly instructions that are generated will be basically the same as the ones for while-loops in imperative style.

Your function is not tail-call optimizable because the recursion is not the last step. It needs to return first and then it can add x to the result. Usually this is easy to get around, you just create a helper function that passes an accumulator along with the other parameters

let rec sum x =
  let sum_aux accum x =
    if x > 1 then sum_aux (accum + x) (x - 1)
    else x
  in sum_aux 0 x;;