In most cases, you will not need to write your own custom recursive functions. You can usually rely on functions like
List.map to transform data and functions like
List.foldl to crawl over values and accumulate some information. Definitely prefer this approach!
Now, that said, you will occasionally find cases where you want to write your own recursive functions. I think most programmers just feel how to write functions like this, but that is extremely unhelpful as advice! I introspected on how I write recursive functions, and I recognized two major strategies that I use all the time. I hope they help you out!
Strategy One - Pretend You Are Done
When writing recursive functions, there are two crucial steps:
- Start with a
case. Destructure your data and see how far you can get with each branch.
- Pretend you are done. Pretend you already implemented the function and try to use it!
So imagine we want to get the length of a list without
List.foldl. Step one is to use
case on our list:
length : List a -> Int length list = case list of  -> ... first :: rest -> ...
Great, those are the two scenarios. If the list is empty, the length is zero, so we can fill that in.
length : List a -> Int length list = case list of  -> 0 first :: rest -> ...
In the other case, we get the
first value and another list representing the
rest of the values in the list. Well, we know we have one value, but how long is the
rest? Remember step two: pretend you are done. That is what
length is supposed to do, so let’s just use that!
length : List a -> Int length list = case list of  -> 0 first :: rest -> 1 + length rest
It definitely takes time to get your brain trained to think this way, just like it took time for
for loops to feel natural. The only way to improve is to practice! Speaking of practice...
Exercise: Define a
sumfunction that adds up all the integers in a list.
sum : List Int -> Int sum list = ...
Remember to (1) use
caseand (2) pretend you are done!
Strategy Two - Helper Functions
The “pretend you are done” strategy is neat, but sometimes it is not enough. If you ever find yourself thinking that you feel like you need more information to make it work, it is time to create a helper function! Let’s see how this works with the
reverse : List a -> List a reverse list = ...
One way to approach this would be to chomp elements from one list and put them directly on a second list like this:
This means we want to keep track of a second list as we recurse through the first list. When you need extra information, break the recursion into a helper function with more arguments like this:
reverse : List a -> List a reverse list = reverseHelp list  reverseHelp : List a -> List a -> List a reverseHelp list reversedList = ...
reverseHelp function is going to be recursive, so like always we should try to (1) use
case and (2) pretend we are done. So first we break up the
reverse : List a -> List a reverse list = reverseHelp list  reverseHelp : List a -> List a -> List a reverseHelp list reversedList = case list of  -> ... first :: rest -> ...
list is empty, we want to give back the
list has a
first element, we want to put it on
reversedList and keep going.
reverse : List a -> List a reverse list = reverseHelp list  reverseHelp : List a -> List a -> List a reverseHelp list reversedList = case list of  -> reversedList first :: rest -> reverseHelp rest (first :: reversedList)
And there we go, a
fooHelp pattern is quite common. The
fooHelp part lets you carry around extra state as you recurse through some data structure, and the
foo part lets you hide those details from people using the function. So
reverseHelp carries an extra list around, and
reverse gives the initial
 to make the public API nicer.
Like with the first strategy, the best way to get used to thinking this way is to practice!
lengthwith strategy two. Only make changes in
length : List a -> Int length list = lengthHelp list 0 lengthHelp : List a -> Int -> Int lengthHelp list lengthSoFar = ...
When you get that, do the same for the
sum : List Int -> Int sum list = ...
For the sake of this exercise, the
sumfunction can never call itself!
We covered the two main strategies in writing recursive functions:
caseand pretend you are done.
- Create a
fooHelpfunction that carries extra state around.
Both come up any time you need to write a recursive function yourself. That should be relatively rare given library functions like
Dict.map, etc. but at least now you are better prepared for when the time comes!
Finally, it definitely takes some time to get used to thinking this way, just like it took time to get used to thinking with
for loops. Do not get discouraged! It is hard for everyone at first, and the only real way to get acclimated is to practice!
More Exercises: A great way to practice writing recursive functions is to try to implement everything in the
Listlibrary yourself. Some good ones to try are:
member : a -> List a -> Bool
take : Int -> List a -> List a
drop : Int -> List a -> List a
repeat : Int -> a -> List a
range : Int -> Int -> List Int
map : (a -> b) -> List a -> List b
map2 : (a -> b -> result) -> List a -> List b -> List result
Try using strategy one and two on each and see how they go. Try to get a feel for when to reach for them.