Small disclaimer : I’m an Impostor and I’m not the nerdiest math engineer to speak about recursion which is such a heavy topic. Instead, I will speak about my experience and how recursion can help solve “cleanly“ daily problems.
Simple, but soooo complex
Few years ago, the first time I encounter a recursion it was with a more experienced dev colleague who gave me that solution to solve a particular situation that I had. I was like : “Great! but wait… what?!?”
The problem with recursive functions is to be able to understand them. It’s a bit like loops, but only for the “and again! and again! and again! ….” part. So yes, you will quickly have a lot of
console.log everywhere, without understanding much more what you are doing.
The magic recipe
To code a nice recursive function, you must pay attention to the following points if you don’t want to spend a lifetime in a try-fail loop :
- The recursion (no shit) : when the method will call itself.
- Proper conditions : to define when it returns things or not in order to prevent failure.
- Pureness : first and second rule of the functional programming club
For example, if you want to get the index of a specific array value :
Yes, I’m aware that
starks.indexOf('Arya') is a faster an cleaner way to do it, not that a noob…
This first example is a recurring one. Very often, when you want to call some data from an API, for some reason you want them all at once. So you will fetch the first endpoint, get the data, call the next “page” and so on until there is no more “page” to fetch. It’s very dangerous and stupid if there is a lot of “pages” and anything went wrong in the process, but that’s your call at the end ¯_(ツ)_/¯
In this example, we will use SWAPI to get all the universe’s species :
Because we are calling an asynchronous method through
axios, we must use
Promise to solve this case. So each time the method calls a new endpoint, it will add the response data to the payload and continue until there is no more endpoint to call. To resolve the initial Promise, we can pass the
resolve function as a argument. (Feel free to comment if you have a better way to do it). Even if it’s not the nicest way to do it, it’s a good example of recursion and promises.
Each Christmas (not the most inclusive example I know), we are doing the secret Santa in my family. In order to not have to cut small pieces of paper, put them in a hat and draw yourself at the end, I directly code a small JS script to do it using text messages.
So basically I have an array of peoples with their names and phone number and I must assign a name to each number which is not itself. I tried many approaches and the most recent one was to combine the famous The Fisher-Yates (aka Knuth) shuffle algorithm with a small validation method to check that no name was assigned to it own phone number.
Finally, it looks like :
Full project on GitHub.
It’s not a single recursive function, but more a mix of multiple methods using mainly the
while operator. Remember, you can surely build complex recursive methods, but I you want to understand it months or even years later, you better have to keep things simple and understandable.
Not longer than a week ago, I face some issue of retrieving unpredictable data out of a headless CMS through Gatsby GraphQL query language. Because in this big data object I can only predict the parent attribute and not all the nested sub-attributes, my solution was to flag those parents and
JSON.stringify them with a recursive method. They can be at any level, so I had to traverse the data response object, level by level, and stringify it when I found the right flag.
At the end, a simple traversing method, but not simple for me to write ^^’
I still don’t run any performance tests to see if there are some less consuming approaches, but it remains a good example of deep object traversing with recursion.
I’m sure everybody who uses recursion weekly has a lot of good examples. I encourage you to share your proudest recursive functions and discuss them with the community to be more efficient each time you have to write one.
Honestly, it’s still hard and time consuming for me to write them. Maybe it’s because I’m not a proper engineer or maybe because it’s hard for everyone (reassure me please ^^’). Anyway, it’s a very powerful way solve things and it will keep your code small and something, simple to read and to understand.