# Use cases for recursive functions

**URL:** <https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557>\
**Category:** Learn\
**Created:** [April 26, 2019, 4:40am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557 "2019-04-26T04:40:52Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 4:40am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/1 "2019-04-26T04:40:52Z")

</div>

Hi there,  
for my master thesis I need to formally define the Elm language. (more on that at a later date) I really want to say that Elm has no run-time errors, that would make things a lot easier. From what I understand Elm uses Recursion without checking its termination and therefore will always run into run-time errors.

I would like to use this topic to get a feeling for how many people actually use recursive functions in their code, why and if it could be avoided/if I can ignore recursive functions in my formal definition.

- How often do you use recursive function calls?
- Could these recursive function be also written using `fold, map, filter`?
- If so, why do you choose recursive function instead? Is it like in my `find` example, where I’m just optimizing efficiency or does it have other reasons?

* * *

So I’ll start with my experience with recursive functions. The only time I really needed to use them was when I wanted to exit out of the fold-function:

```elm
{-| calling `find true` will always run though the entire list
-}
find : (a -> Bool) -> List a -> Maybe a
find condition =
    List.filter condition >> List.head

{-| Now the function actually aborts once it has found a valid candidate.
-}
findRec : (a -> Bool) -> List a -> Maybe a
findRec condition list =
   case list of
       head :: tail ->
           if head |> condition then
               Just head
           else
               findRec condition tail 
       [] ->
           Nothing

```

For function where I my self don’t know when it stops, I usually use the update-function for each iteration:

```auto
update : Msg -> Model -> (Model, Cmd Msg)
update msg ({x} as model) =
    case msg of
        Approximate ->
            let
                newX = iterate x
            in
            ( {model| x = newX}
            , if newX |> isGoodEnough(x) then
                  Cmd.none
              else
                  Task.perform (always Approximate) (Task.succeed ())

```

It would be interesting to know how many of you also use the update-function like I do.

---

<div class="post-metadata">

**Author:** ![MartinS](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/martins/32/3137_2.png) [@MartinS](https://discourse.elm-lang.org/u/MartinS)\
**Post date:** [April 26, 2019, 7:04am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/2 "2019-04-26T07:04:33Z")

</div>

> Hi there,  
> for my master thesis I need to formally define the Elm language. (more on that at a later date) I really want to say that Elm has no run-time errors, that would make things a lot easier.

Sorry, I’m not answering your question directly but here I’d like to add that even if you ignore runtime errors caused by recursion, there are still other runtime exceptions. Testing two functions for equality will cause a runtime exception (though hopefully this will become a compile time error in the future) and if your app runs out of memory that will also cause a runtime exception (I doubt this can be prevented).

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 7:49am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/3 "2019-04-26T07:49:35Z")

</div>

> [@MartinS](#):
>
> Testing two functions for equality will cause a runtime exception (though hopefully this will become a compile time error in the future) and if your app runs out of memory that will also cause a runtime exception (I doubt this can be prevented).

Thanks for the input. For my formal language, memory does not matter, but function equivalence definitely does. I need to think about that.

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [April 26, 2019, 10:19am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/4 "2019-04-26T10:19:49Z")

</div>

> [@Lucas\_Payr](#):
>
> For function where I my self don’t know when it stops, I usually use the update-function for each iteration:

It seems a curious approach to only recurse through the `update` function. I think you will find this runs much quicker:

```
update : Msg -> Model -> (Model, Cmd Msg)
update msg ({x} as model) =
    case msg of
        Approximate ->
            ({ model | x = approx x}, Cmd.none)

approx : X -> X
approx x =
    let
        newX = iterate x
    in
        if isGoodEnough x newX then
            newX
        else
            approx newX

```

If `approx` takes a long time, this can freeze the UI, as no other `Cmd`s will run during the calculation. You can work around that by either splitting the approximation into batches of iterations (say 10, 100, 1000, … it depends on what you are calculating). Another approach is to JSON encode the inputs and outputs to the calculation and pass to another Elm process running in a background thread as a web worker.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 10:56am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/5 "2019-04-26T10:56:49Z")

</div>

> [@rupert](#):
>
> It seems a curious approach to only recurse through the `update` function. I think you will find this runs much quicker:

As I said before

> [@Lucas\_Payr](#):
>
> I would like to use this topic to get a feeling for how many people actually use recursive functions in their code, why and if it could be avoided/if I can ignore recursive functions in my formal definition.

My approach intentionally tried to avoid a recursive function call, because it might be that my approximation never stops (in case `isGoodEnough(x,newX) == False`).

But I’m really not interested in ways how things could be done, I’m interested in knowing:

- How often do you use recursive function calls?
- Could these recursive function be also written using `fold, map, filter`?
- If so, why do you choose recursive function instead? Is it like in my `find` example, where I’m just optimizing efficiency or does it have other reasons?

I’ll add these questions to my original post.

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [April 26, 2019, 11:07am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/6 "2019-04-26T11:07:24Z")

</div>

`fold`, `map`, `filter` etc are all defined using recursion, since `List a` is a recursive datatype.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 11:23am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/7 "2019-04-26T11:23:46Z")

</div>

> [@ilias](#):
>
> `fold` , `map` , `filter` etc are all defined using recursion, since `List a` is a recursive datatype.

Yes. But they are also build-in functions and one can trust that they will terminate.

For my master-thesis I will need to write a mathematical definition of Elm, meaning I need to describe mathematically the things that the compiler does. For me it’s no problem at all to add `fold, map, filter` as build-in expressions. (similar to the way `while,for,do` are used in other languages, even it they could be also written using recursion)

But my mathematical definition should also be able to handle a typical code from the real world. In case that recursive function are but mostly not used (or only for optimization), I could ignore them all together.

---

<div class="post-metadata">

**Author:** ![ilias](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/ilias/32/6_2.png) [@ilias](https://discourse.elm-lang.org/u/ilias)\
**Post date:** [April 26, 2019, 11:36am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/8 "2019-04-26T11:36:10Z")

</div>

Alright. In my experience, recursion is a very common pattern, both in library as well as in application code. Since Elm is turing complete, termination cannot be proven, but in practice, that turns out not to happen very often.

Anecdotally, I have this to share: back in 0.18 days, there was a code-generation issue when dealing with certain recursive patterns (json decoders, parsers, etc) using `lazy` which could in practice result in runtime errors. This happened enough for me to write [an article](https://blog.ilias.xyz/help-my-recursive-decoder-caused-a-runtime-exception-453d46a99e1e) detailing how this happens and how to prevent it. So, me deduction goes as follows:

- people generally write recursive decoders for recursive data structures
- people wrote enough such decoders that I got tired answering the same questions
- the only way to use recursive data structures, is through recursion
- people generally write decoders for use in application code  
-\> recursive code in applications is fairly common.

I personally wouldn’t feel very comfortable with characterising functions like `foldl` as language constructs rather than plain old library functions, but that’s sort of besides the point, so let’s hold off on that discussion 🙂

---

<div class="post-metadata">

**Author:** ![Herteby](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/herteby/32/1329_2.png) [@Herteby](https://discourse.elm-lang.org/u/Herteby)\
**Post date:** [April 26, 2019, 3:32pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/9 "2019-04-26T15:32:47Z")

</div>

Btw, I heard that in the future the type system may actually catch attempts at comparing functions, and any types containing functions.

---

<div class="post-metadata">

**Author:** ![1hko](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/1hko/32/1328_2.png) [@1hko](https://discourse.elm-lang.org/u/1hko)\
**Post date:** [April 26, 2019, 3:33pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/10 "2019-04-26T15:33:24Z")

</div>

> [@Lucas\_Payr](#):
>
> If so, why do you choose recursive function instead? Is it like in my `find` example, where I’m just optimizing efficiency or does it have other reasons?

Your `find` is not optimizing efficiency. `List.filter` will iterate through the _entire_ list, even after the first result is found. A recursive solution could terminate immediately.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 3:35pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/11 "2019-04-26T15:35:10Z")

</div>

> [@1hko](#):
>
> Your `find` is not optimizing efficiency. `List.filter` will iterate through the _entire_ list, even after the first result is found. A recursive solution could terminate immediately.

Exactly. Thats my point. Thats the reason I gave the example.

Maybe that was not clear… I will add the recursive function to the example.

---

<div class="post-metadata">

**Author:** ![allanderek](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/allanderek/32/1360_2.png) [@allanderek](https://discourse.elm-lang.org/u/allanderek)\
**Post date:** [April 26, 2019, 4:45pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/12 "2019-04-26T16:45:07Z")

</div>

If you have built a recursive data structure you will often _have_ to write at least one recursive function to accompany it. For example the elm-i18next library has a `Tree` data-structure representing a hierarchy of translations: [https://github.com/ChristophP/elm-i18next/blob/4.0.0/src/I18Next.elm#L49](https://github.com/ChristophP/elm-i18next/blob/4.0.0/src/I18Next.elm#L49) it therefore pretty much necessarily has to define a recursive function `foldTree`: [https://github.com/ChristophP/elm-i18next/blob/4.0.0/src/I18Next.elm#L147](https://github.com/ChristophP/elm-i18next/blob/4.0.0/src/I18Next.elm#L147)

---

<div class="post-metadata">

**Author:** ![turboMaCk](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/turbomack/32/355_2.png) [@turboMaCk](https://discourse.elm-lang.org/u/turboMaCk)\
**Post date:** [April 26, 2019, 5:01pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/13 "2019-04-26T17:01:46Z")

</div>

> [@Lucas\_Payr](#):
>
> - How often do you use recursive function calls?
> - Could these recursive function be also written using `fold, map, filter` ?
> - If so, why do you choose recursive function instead? Is it like in my `find` example, where I’m just optimizing efficiency or does it have other reasons?

we use recursion heavily preferably using functions like folds or find. Also we has our domain specific recursive datastructures which I don’t think is uncommon and for those we implement folds and traversals used in business logic. Also often even views are recursing (trees).

Unfortunetely I can’t offer access to code for analysis to whole app but this package (we use extensively) is also a good example [GitHub - turboMaCk/lazy-tree-with-zipper: Lazy rose tree (multiway tree) with zipper. In Elm](https://github.com/turboMaCk/lazy-tree-with-zipper)

More broadly…  
“no runtime exceptions” is marketing claim. Reality is more like “avoiding avoidable runtime exceptions within what is believed to be reasonable tradeoff by authors”. We know that infinite recursion is a problem in any turing complete laguage. You can try to detect some fix point things like Idris does for instance but won’t be able to detect every single one anyway (formaly proven). Function equality was already metioned as another example of runtime exceptions - that’s due to lack of `eq` “type class”. I also encourage you to check totality checks for recursive functions in Idris as it might be relevant to your work.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 26, 2019, 5:39pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/14 "2019-04-26T17:39:21Z")

</div>

> [@turboMaCk](#):
>
> “no runtime exceptions” is marketing claim. Reality is more like “avoiding avoidable runtime exceptions within what is believed to be reasonable tradeoff by authors”. We know that infinite recursion is a problem in any turing complete laguage.

Thanks for your response. I believe there will not be a way around both exceptions and recursive functions.

> [@turboMaCk](#):
>
> You can try to detect some fix point things like Idris does for instance but won’t be able to detect every single one anyway (formaly proven).

I don’t believe that I will be using fix point theory. I might be confusing this with something else, but I believe my adviser models functions as relations instead.

The thesis is still in its beginning stage. Currently, I am trying to figure out what exactly I want to do, that aspects are the most important and so on. I’ll close this topic for now, and will come back to you once my thesis is in a stage where I can give more detail about what I am actually doing. Thanks, you all, you really helped me a lot.

---

<div class="post-metadata">

**Author:** ![Chadtech](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/chadtech/32/609_2.png) [@Chadtech](https://discourse.elm-lang.org/u/Chadtech)\
**Post date:** [April 26, 2019, 11:02pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/15 "2019-04-26T23:02:58Z")

</div>

> [@Lucas\_Payr](#):
>
> How often do you use recursive function calls?

A lot. I estimate I write a recursive function for every 1500 lines of code I write.

> [@Lucas\_Payr](#):
>
> Could these recursive function be also written using `fold, map, filter` ?

I think most of my recursive functions could be substitued with a `fold`.

> [@Lucas\_Payr](#):
>
> If so, why do you choose recursive function instead? Is it like in my `find` example, where I’m just optimizing efficiency or does it have other reasons?

Well, I think recurive functions have a lot more flexibility. Its easier for me to just think through what behavior I want to happen, and what type signature I need my functions need, than it is for me to start with `fold : (a -> b -> b) -> b -> List a -> b` and try and fit what I am trying to do into that mold.

But honestly its probably mostly just habit.

---

<div class="post-metadata">

**Author:** ![turboMaCk](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/turbomack/32/355_2.png) [@turboMaCk](https://discourse.elm-lang.org/u/turboMaCk)\
**Post date:** [April 28, 2019, 11:28am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/16 "2019-04-28T11:28:48Z")

</div>

> [@Lucas\_Payr](#):
>
> I don’t believe that I will be using fix point theory. I might be confusing this with something else, but I believe my adviser models functions as relations instead.

If I understand it then you probably want to disallow recursion in language and define all recursive functions like `folds` and `find` as a language construct. I believe that would me language you’re left with is not turing complete.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [April 28, 2019, 11:42am UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/17 "2019-04-28T11:42:56Z")

</div>

> [@turboMaCk](#):
>
> If I understand it then you probably want to disallow recursion in language and define all recursive functions like `folds` and `find` as a language construct. I believe that would me language you’re left with is not turing complete.

Yes, that was the plan. But I’ve already thrown that idea away.

---

<div class="post-metadata">

**Author:** ![HappMacDonald](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/happmacdonald/32/1069_2.png) [@HappMacDonald](https://discourse.elm-lang.org/u/HappMacDonald)\
**Post date:** [May 2, 2019, 2:55pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/18 "2019-05-02T14:55:43Z")

</div>

You know, with all of this discussion of recursive data structures, I haven’t heard anybody opine about whether or not Lucas\_Payr’s “use the update function for all recursion” approach would … at least in principal … work.

Because update can abuse the Task system to call itself indefinitely, and any function can call update and use the Msg to differentiate their needs, then _at least in theory_ I suspect that every recursive call could be transformed into an update call.

But that leaves me wondering about the ultimate relevance of recursion to your thesis if a structurally identical mechanism already exists, Lucas\_Payr. 🤔

---

<div class="post-metadata">

**Author:** ![rupert](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/rupert/32/1775_2.png) [@rupert](https://discourse.elm-lang.org/u/rupert)\
**Post date:** [May 2, 2019, 4:03pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/19 "2019-05-02T16:03:40Z")

</div>

> [@HappMacDonald](#):
>
> You know, with all of this discussion of recursive data structures, I haven’t heard anybody opine about whether or not Lucas\_Payr’s “use the update function for all recursion” approach would … at least in principal … work.

Perhaps, but it does add a considerable overhead. For example, you would not write some recursive data structure this way - it would be inconvenient to break up the iterations into Tasks or Cmds as well as slow.

Theoretically I don’t see why not - you just need to create a continuation to carry on from in the next update. Note also, this means putting continuation functions either in the Model or in the Msg - but perhaps they can also be captured inside a Task.

---

<div class="post-metadata">

**Author:** ![Lucas\_Payr](https://yyz1.discourse-cdn.com/flex035/user_avatar/discourse.elm-lang.org/lucas_payr/32/4993_2.png) [@Lucas\_Payr](https://discourse.elm-lang.org/u/Lucas_Payr)\
**Post date:** [May 2, 2019, 4:16pm UTC](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557/20 "2019-05-02T16:16:34Z")

</div>

> [@HappMacDonald](#):
>
> But that leaves me wondering about the ultimate relevance of recursion to your thesis if a structurally identical mechanism already exists, Lucas\_Payr. 🤔

I think you’re on to something, I didn’t even think about adding the full Elm Architecture to my formal language 🤔

> [@rupert](#):
>
> Theoretically I don’t see why not - you just need to create a continuation to carry on from in the next update. Note also, this means putting continuation functions either in the Model or in the Msg - but perhaps they can also be captured inside a Task.

The more I think about it, the more I like this idea. As long as I show that every recursive function can somehow be implemented in TEA, I don’t even need to worry if its done with a lambda function, Msg or a Task.

But maybe I’m missing something and I’m actually making things more complicated than it would have been with normal recursion.

Anyway, [HappMacDonald](https://discourse.elm-lang.org/u/HappMacDonald), [rupert](https://discourse.elm-lang.org/u/rupert), thanks for that input.

[Next page](https://discourse.elm-lang.org/t/use-cases-for-recursive-functions/3557.md?page=2)