Introduction
Recursion is a powerful way of solving certain problems that we face in our programs, but it's difficult to get your head around of it at first. One of the reasons is that recursion can look quite complicated when you see it for the first time. But there are actually many practical uses of recursion that are useful to us programmers on a day-to-day basis.
If you've never used recursion before, or you don't see a place for it in web development, this article is going to explain everything you need to know about it. We will take a look at what recursion is, how it works, and how it might help us in building web applications.
What is recursion?
There are many definitions of recursion on the internet, many of them are difficult to understand. I like to describe it shortly. In computer science, recursion is the process in which a function calls itself.
The function that calls itself is called as recursive function.
def hi():
return hi()This is the simplest possible way of defining a recursive function, although it's not very useful because it runs an infinite number of times until it will crush our program.
In imperative languages we use loops like for to iterate over the array to get the results we want, but what happens when we have an array of arrays, and inside that nested arrays we also have children arrays. How do we iterate over them?
One of the solutions could be to write a for loop, and a for loop inside, and then another loop as a child of the second loop, and so on. It goes pretty gross very fast, but it works.
The problem comes when we don't know what array we're going to get and how many nested arrays we'll get. That's where recursion comes in.
Basic example of recursive function
To understand the example that I'm going to give you, you need to know what a factorial of a number is. To find a factorial of a number, we basically need to multiply all whole numbers from our chosen number down to 1.
1! = 1
4! = 4 × 3 × 2 × 1 = 24
7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
Let's see the example of a function definition written in Python that calculates a factorial of a number.
def fact(n):
if n == 1:
return 1
return n * fact(n - 1)If we print the result of this function with number 3 as first argument, the result will be 6.
print(fact(3))The function fact will run 3 times. First it will return 3 * fact(2), after this it will return 2 * fact(1) and on the last run it will return 1 because n == 1 and in our condition if n == 1 return 1.
In web development we don't usually use factorials and other math calculations, even if we need to do that, we have special functions built-in into the languages. Recursion helps with other problems in web development than math, that's why I decided to write this article.
Use cases in web development
I've never though that recursion was something that I'm going to use regularly in web development. I thought that it's only going to help me in solving Katas on Codewars. But when I've tried to implement it in one of my projects, I started seeing familiar patters in other projects as well. Here is the recursive method that I have in one of my old projects.
class Helper
{
public static function unwrapArray(array $array): array
{
$result = [];
foreach ($array as $arr) {
if (!is_array($arr)) {
$result[] = $arr;
continue;
}
$result = array_merge($result, self::unwrapArray($arr));
}
return $result;
}
}You don't need to be a PHP programmer to understand what it does, it just takes an array with any amount of nested arrays and makes it a one dimensional array.
$arr = [['Some', 'Nice'], ['Cool', 'Fine', ['Smile', ['Joy']]]];
$res = Helper::unwrapArray($arr);
// result: ['Some', 'Nice', 'Cool', 'Fine', 'Smile', 'Joy']You can do a million things with multidimensional arrays in web development. I've found many cases where I would reach for recursive implementation instead of using loops or looking for a library that does the same job.
In the last project that I was working on, I had to display 380 categories that have nested children categories and those have more nesting. Some category might have 3 children and some might have 5. We don't know how deep the array is.
Here is the small part of the list of categories generated in HTML.
The list is very long, so if you want to see the whole list, I have a link for you.
I couldn't display all the categories without a recursive function, that's why I've used it here. I've accomplished needed results with a small amount of code.
Building a list of links
For this tutorial, instead of building a nested categories tree, we'll build a list of links that will be printed in HTML into the browser.
For this example, we'll have a JavaScript array that represents our list structure with few nested children items.
list = [
{
name: 'Home',
href: '/',
children: [],
},
{
name: 'More',
href: '/more',
children: [
{
name: 'About me',
href: '/more/about-me',
children: [
{
name: 'Life',
href: '/more/about-me/life',
children: [
{
name: 'Blogging',
href: '/more/about-me/life/blogging',
children: [],
},
{
name: 'Hobby',
href: '/more/about-me/life/hobby',
children: [],
},
],
},
{
name: 'Career',
href: '/more/about-me/career',
children: [],
},
],
},
{
name: 'Languages',
href: '/more/languages',
children: [],
},
],
},
]Our task is to write a function that will convert a list array into HTML markup. Let's write a skeleton first.
function convertListToHtml(list) {
//
}
console.log(convertListToHtml(list))First, we need to iterate through the list and check if the item has children, or it doesn't.
function convertListToHtml(list) {
let html = ''
for (item of list) {
if (item.children.length === 0) {
html += `no children,`
} else {
html += `has children,`
}
}
return html
}In our console we see printed no children,has children, because our first item doesn't have children and the second has 2. We need to make so that if it doesn't have children, then convert the item into HTML. Let's do it.
function convertListToHtml(list) {
let html = '<ul>'
for (item of list) {
if (item.children.length === 0) {
html += `<li><a href="${item.href}">${item.name}</a></li>`
} else {
html += ``
}
}
return html + '</ul>'
}In our console, we see:
<ul><li><a href="/">Home</a></li></ul>Now is the fun part, we'll use recursion and call the convertListToHtml function inside the convertListToHtml function.
We need it because we know that this function converts the list of menu items into HTML, that's what we exactly need for our children.
function convertListToHtml(list) {
let html = '<ul>'
for (item of list) {
if (item.children.length === 0) {
html += `<li><a href="${item.href}">${item.name}</a></li>`
} else {
html += `<li>
<a href="#">${item.name}</a>
${convertListToHtml(item.children)}
</li>`
}
}
return html + '</ul>'
}In our console, we'll see the correct HTML that we wanted. After formatting, it looks like this:
<ul>
<li><a href="/">Home</a></li>
<li>
<a href="#">More</a>
<ul>
<li>
<a href="#">About me</a>
<ul>
<li>
<a href="#">Life</a>
<ul>
<li><a href="/more/about-me/life/blogging">Blogging</a></li>
<li><a href="/more/about-me/life/hobby">Hobby</a></li>
</ul>
</li>
<li><a href="/more/about-me/career">Career</a></li>
</ul>
</li>
<li><a href="/more/languages">Languages</a></li>
</ul>
</li>
</ul>Here is how it looks in browser without CSS.
The last step that we need to make is to refactor our function. I constantly do it after seeing that the function works as expected.
Let's use a ternary operator instead of if/else because I don't like the keyword else in my code.
function convertListToHtml(list) {
let html = '<ul>'
for (item of list) {
html += item.children.length === 0
? `<li><a href="${item.href}">${item.name}</a></li>`
: `<li><a href="#">${item.name}</a>${convertListToHtml(item.children)}</li>`
}
return html + '</ul>'
}Moreover, I want to rename the variable html to a result, I always do that for variables that are being returned from functions. That way, if I see a variable result somewhere in my function, I know that it will be returned in the end.
function convertListToHtml(list) {
let result = '<ul>'
for (item of list) {
result += item.children.length === 0
? `<li><a href="${item.href}">${item.name}</a></li>`
: `<li><a href="#">${item.name}</a>${convertListToHtml(item.children)}</li>`
}
return result + '</ul>'
}Conclusion
Recursion is not something that you're going to use everywhere in your code. I would personally reach for it only when I see a familiar pattern for using it.
Like we saw in my examples, the pattern is pretty clear, it's a multidimensional array with many children. Remember that languages that you're working with might already have a built-in functionality for doing certain recursive operations. And they are probably fast and easy to read.
Everything you've read about in this article is just the tip of the iceberg. The best way to learn recursion is to have a solid foundation on the basics of programming in general. Then you can move on to more complicated problems when you've become comfortable with the basics.
Just try it, you will be surprised how it can help you in building more complex UIs and programs.
❤️ Thanks to Benoit Beaumatin for the beautiful photo for this post.
Keywords: navbar
