Once you get pattern matching and recursion, you are set
I remember googling pattern matching and recursion, hoping to watch a couple of videos and be set with both skills in the time it takes to make coffee and take a shower.
That was a couple of months back. That should give you a clue.
In this article, I am going to leave aside the questions "what is recursion" and "why should I use it". Recursion exists and, if we are developing with Elixir, we need to know it. Period. Next, please.
Now that we need to contend with recursion, my aim is to shed light on the two types of recursion I know to exist: regular recursion, and tail recursion.
Regular Recursion
In regular recursion, a function calls itself while it is in the middle of doing something.
This is like me, when I walk into my bedroom and run the function "tidy_this_thing_up" and, in doing so, I open a closet, where I run the function "tidy_this_thing_up" again, and open a drawer, where I run the function "tidy_this_thing_up", and I find an old hard drive there, and carelessly plug it in, so I can run "tidy_this_thing_up" for the fourth time.
Two problems arise with this model.
First, we need to define when to stop. We need to call it quits at some point, because I have not yet started to tidy up my room, but somehow I am finding myself reorganizing photos of a summercamp that happened 20 years ago.
I need a base case, a place where I can tell my function: "you are done".
The second problem is memory, resources... keeping track of all I am doing. By the time I am organizing my external hard drive, my brain may have completely forgotten about my untidy room, closet and drawer. That'd be a stack overflow or a memory collapse.
OR, if I am extremely resourceful, I will finish organizing my hard drive, and go back to the drawer, tidy it up, return to the closet, tidy it up... My list of pending tasks has been growing and, if I am a man of my word (and functions tend to be), I need to follow my breadcrumbs back and complete all the pending tasks I have been leaving half-cooked along the way.
It is taxing but, if I run my functions this way, I will end up with a tidy room.
Tail Recursion
With tail recursion we do not call the function tidy_this_thing_up in the middle of tidying something up. We call it again once we have finished tidying something up and can move to something else.
Immediately this seems cleaner, easier, more elegant. The steps required do not accumulate one on top of another, with a potentially eternal list of pending tasks that were never finished and that are holding part of our resources hostage.
Tail recursion would ask us to do something, finish it, and then do it again.
In my tidy the bedroom example, I would find a way to organize the major task into sub-tasks that I can complete before I start a new task.
One potential implementation, maybe not the only one, would be to have the tidy_this_thing_up function to keep a list of sub-elements that need tidying.
I would walk into my room, notice three bookshelves, two closets and that chair with clothes (you know the one). That makes a list of five things to tidy up.
I successfully run my function on bookshelf1, then bookshelf2, then bookshelf3, then closet1, and there I find my drawer but, instead of halting the task of cleaning up my closet (Eminem dixit), I simply add "drawer1, drawer2, drawer3" to my list of things to tidy up, I finish tidying up my two closets, my chair_with_clothes, and then I go tackle the drawers one by one.
(We still need to have a criteria for when to stop and call it a day)
Final thoughts
One of my mentors at Dockyard Academy put me through the exercise of writting each step of the process of a recursive function (on paper, the nerve!).
First, he made me write out the regular version, then the tail recursive version.
Both exercises were herculean efforts: pick a pen and use it to think (on paper, the nerve!).
Kidding aside, I do recommend this exercise to anyone studying Elixir or wanting to really (really) understand what recursion is doing. It forces the brain to internalise recursion processes.
At the moment of writing this, I feel that tail recursion is elegant, efficient, economic, and regular recursion is a potential uncontrollable mess. I know I am just being dramatic (mixing feelings with coding, how dare I). There may be use cases for both, I am sure.
Who doesn't enjoy the thrill of danger of a stack overflow, anyway?
All of this makes me think of the old regular recursive fights with a certain ex-girlfriend. The stack kept piling s**t up and nothing ever got solved.
As I grow older (hopefully wiser), I prefer my conflict-resolution tail recursive: fixing one thing, and going for the next one. It actually works wonders. Sometimes even writing it on paper helps.
Top comments (0)