Avoiding "RangeError: Maximum call stack size exceeded"

I have a recursive function that is crashing with a RangeError: Maximum call stack size exceeded error, but it seems like it shouldn’t.

My code is at https://ellie-app.com/gdwKVjzNPnHa1, and the problematic function (turtleStepsToPointsHelper in my code) has the overall structure:

turtleStepsToPointsHelper: Point -> Float -> Float -> List TurtleSteps
turtleStepsToPointsHelper initialPosition orientation stepSize steps =
    case steps of
        [] ->

        Forward :: rest ->
                nextStep = ...
            nextStep :: turtleStepsToPointsHelper nextStep orientation stepSize rest

        Left :: rest ->
            turtleStepsToPointsHelper initialPosition (orientation + pi / 2) stepSize rest

        Right :: rest ->
            turtleStepsToPointsHelper initialPosition (orientation - pi / 2) stepSize rest

I’m new to Elm (but know some Haskell and functional programming stuff), and it seems like that’s the right way to do it.

  • is this a compiler bug / thing? Some other posts here suggest that it might be.
  • is my code idiomatic Elm? Is there a different way, better style, etc?
  • forgetting about elegant style and so on, is there at least some workaround?
1 Like

I copied your Ellie locally and compiled with elm make src/Main.elm. Sometimes its helpful to see the compiled code to figure out where things are not tail recursive. For the Forward case I get:

case 'Forward':
    var _n1 = steps.a;
    var rest = steps.b;
    var nextStep = A2(
            {x: stepSize, y: 0},
    return A2(
        A4(author$project$Main$turtleStepsToPointsHelper, nextStep, orientation, stepSize, rest));

Elm is definitely not as advanced as Haskell is when it comes to detecing that things can be tail recursive. One thing to note is that |> and <| seem like they should be eliminated as syntactic sugar, but in fact get turned into function calls, and can often prevent tail recursion. (That does not seem to be the case this time).

I think what is missing is that Elm does not have the tail recursion modulo cons optimisation:

I think instead of consing on nextStep, can it simply be added into the result list of turtleStepsToPointsHelper? Then have a pass at the end to extract them all into a list? The details are a little hazy and I am being called to lunch, but something like that may work…

Hey @dandrake! This topic can be tricky without a good intro to stack usage, so check out this explanation of “tail call elimination” to learn why the current code is causing issues in the browser:


It outlines the rewrite technique needed in this case (pass the result list as an argument and reverse it at the end if order is important) that is common in Elm, OCaml, Haskell, Lisp, etc. The larger idea is to turn stack allocations into heap allocations, that way the size of the stack is never a problem for the code.

That resource is just a draft, but I hope it’s helpful nonetheless. And I’m sure someone on here can take it from there in terms of suggesting the specific rewrite for your case!

Aside: It would be cool to have a special error message for this case. If you have time and interest, please add an issue here with this program and the title “better guidance for stack overflows”. I imagine that it might be somewhat frail to detect the exact JS errors for stack overflows across all browsers, but I would love to show a link about tail call elimination at that exact time!

Note: JS is likely to have different stack characteristics than Haskell or OCaml. Maybe stack frames are bigger, maybe the allowed depth is smaller, etc. So the size limit may be reached at different depths in each case. (Laziness in Haskell can also end up putting more things in the heap, which is a complex tradeoff of its own. Sometimes you really want something to be allocated on the stack, thereby making GC pauses less frequent!)


Not 100% sure, but I think this fixes it. It reports:

My depth 6 Koch snowflake has 15626 points.

turtleStepsToPoints initialPosition orientation stepSize steps =
    initialPosition :: turtleStepsToPointsHelper initialPosition orientation stepSize steps []

turtleStepsToPointsHelper : Point -> Float -> Float -> List TurtleSteps -> List Point -> List Point
turtleStepsToPointsHelper initialPosition orientation stepSize steps acc =
    case steps of
        [] ->

        Forward :: rest ->
                nextStep =
                    translate initialPosition (rotate { x = stepSize, y = 0 } orientation)
            turtleStepsToPointsHelper nextStep orientation stepSize rest (nextStep :: acc)

        Left :: rest ->
            turtleStepsToPointsHelper initialPosition (orientation + pi / 2) stepSize rest acc

        Right :: rest ->
            turtleStepsToPointsHelper initialPosition (orientation - pi / 2) stepSize rest acc

As Evan points out, the standard ‘trick’ is to introduce an accumulator to build up intermediate results in, as an explicit stack-on-the-heap.


Thanks @rupert! That was the trick. I was a bit confused about your earlier comment about " instead of consing on nextStep , can it simply be added into the result list of turtleStepsToPointsHelper" and I didn’t know exactly how to set that up. Thanks for the example code showing how easy it is.

@evancz, I will add an issue. And thank you for the link – I have some basic understanding of all the stack and heap allocation stuff, and tail call elimination – but it gets confusing for me because when I look an at pure Elm – such as the code I shared above – I think at one conceptual level (a very pure, functional programming level), but to get this code to work, you have to think at a different conceptual level, one closer to the operating system and the gory details of memory management.

1 Like

I wrote about exactly when tail-call optimization kicks in in Elm, in case you want to know more.

I also wrote a static analysis rule using elm-review that detects (tail-call) unoptimized recursive functions, which can be helpful to detect these ahead of time. I do want to note that not all functions are worth optimizing this way (in some cases, you’re unlikely to ever hit the maximum call stack size), but it’s useful to have a way of detecting this.


Is ‘tail call modulo cons’ implemented in elm-optimize-level-2? I saw some comments around that in the thread linked below. Not sure if level-2 would be a convenient place to implement that, maybe needs to be in the compiler.

1 Like

New issue for a more helpful error message: https://github.com/elm/error-message-catalog/issues/353

I’d like to add that when I first saw the Elm website saying that Elm is “delightful” I was a bit skeptical – but now I agree! I also love the compiler error messages. They are super friendly and helpful. And the help here was fast and, uh, helpful. Thanks.


It is not no. But I have been wondering for a while on how to improve performance of custom list functions that create lists the way OP also did (or rather, do it in the suggested ways because of the stack overflow), and I thank you for letting me know about this thread (I think I somehow missed it back then, or it didn’t register with me), which may give me the piece I was missing. I’m interested in looking into this. I’m not great with scientific literature but I at least have something to read and know the terms in order to look for more.

This topic was automatically closed 10 days after the last reply. New replies are no longer allowed.