Find me on medium
Recursion is a powerful concept in computer programming where a function simply just calls itself. I cannot stress enough how important it is to learn how recursion works as soon as possible after learning the basics.
Understanding the concept of recursion and how to create one will help you think more like a programmer which can help you write more robust code.
Benefits of Recursion
Generally when applying recursion in situations there's almost always these benefits you get from it:
- You save lines of code
- Your code can look cleaner (thus applying clean code practices even if it wasn't your intention)
- It helps save time writing and debugging code
- It reduces the amount of time to run an algorithm (time complexity)
- Helps to easily solve problems when working with tree structures
- Helps to visualize algorithms (Don't believe me?)
Disadvantages of Recursion
- It can be slower--in which it takes up more of the stack (overhead)
- Uses more memory than a loop if tail call optimization isn't used
Do we need it?
In practice, you can perform any algorithm using iteration. The thing is you have to know when it's best to apply recursion--and only that way will make recursion the better choice rather than using iteration.
When applying recursion in situations that work best with it, you unlock the power of recursion just as how powerful it is to apply recursion in the Tower of Hanoi problem.
Examples
A good way to understand recursion is to look at a working code that applies recursion to solve a problem.
Traverse Objects
As mentioned previously, recursions can help easily solve problems when working with tree structures. A deeply nested object is a tree structure, so we'll work with an object.
Pretend that we have an object representing HTML DOM elements, where each nested object object can have children of elements. Each children is another HTML DOM element and can also have children, so it can be a really huge object depending on how many offsprings are produced by their parents.
Our goal is to tap into every single object no matter how far nested it becomes. We'll look at their style property (that represents the attributes for that particular HTML element) and fix the border, textColor and width property to their style representations so that they can be read normally when working with JavaScript.
Here is an example of a style object that needs to be changed:
{
"border": {
"color": "hotpink",
"width": "2px"
},
"textColor": "violet",
"width": "0.45"
}
In html, to color texts we need to use the color property so we would have to transform textColor to color. For width, let's pretend that these decimals represent the percentage of the user's device's viewport (which should be converted to 45vw), and the border object needs to be transformed in a shape like { borderColor: 'hotpink', borderWidth: '2px' }
Let's work with an object that represents that simlar structure so we can traverse it and fix all the style objects:
{
"type": "div",
"style": {},
"children": [
{
"type": "div",
"style": {
"backgroundColor": "black",
"border": {
"color": "hotpink",
"width": "2px",
"style": "dashed"
},
"fontStyle": "italic",
"padding": "20px 25px",
"textColor": "white"
},
"children": [
{
"type": "button",
"style": {
"backgroundColor": "#fda512",
"border": {
"color": "red"
},
"textColor": "#ffffff"
}
},
{
"type": "label",
"style": {
"height": "0.04",
"width": "0.04"
},
"children": [
{
"type": "label",
"style": {
"border": {
"style": "solid",
"width": "5px"
},
"fontStyle": "italic"
},
"children": [
{
"type": "span",
"style": {
"backgroundColor": "#039392",
"borderRadius": "10px",
"height": "0.03",
"outline": "none",
"width": "0.783"
}
}
]
}
]
}
]
}
]
}
Okay, so we have a tree structure going on here where nested objects occur from the children property.
The first thing we're going to create is a transformStyleObject function that takes a style object to fix it, returning a new object that can be worked with normally in JavaScript and the DOM:
function transformStyleObject(styleObj) {
const result = {}
const keys = Object.keys(styleObj)
keys.forEach((key) => {
if (key === 'border') {
const { color, width, style } = styleObj.border
if (color) result.borderColor = color
if (width) result.borderWidth = width
if (style) result.borderStyle = style
} else if (key === 'textColor') {
result['color'] = styleObj.textColor
} else if (key === 'width') {
result['width'] = `${Number(styleObj.width) * 100}vw`
} else if (key === 'height') {
result['height'] = `${Number(styleObj.height) * 100}vh`
} else {
result[key] = styleObj[key]
}
})
return result
}
const result = transformStyleObject({
border: {
width: '2px',
style: 'dashed',
},
height: '0.42',
})
console.log(result) // result: { borderWidth: '2px', borderStyle: 'dashed', height: '42vh' }
We can use regular iteration to traverse objects:
function transformAll({ type = '', style = {}, children = [] }) {
const result = { type, style: transformStyleObject(style), children }
if (Array.isArray(result.children)) {
for (let index = 0; index < result.children.length; index++) {
const child = result.children[index]
child.style = transformStyleObject(child.style)
if (Array.isArray(child.children)) {
for (
let childIndex = 0;
childIndex < child.children.length;
childIndex++
) {
const childsChildren = child.children[childIndex]
childsChildren.style = transformStyleObject(childsChildren.style)
if (Array.isArray(childsChildren.children)) {
for (
let childsChildsChildrenIndex = 0;
childsChildsChildrenIndex < childsChildren.children.length;
childsChildsChildrenIndex++
) {
const childsChildsChild =
childsChildren.children[childsChildsChildrenIndex]
// ...etc
}
}
}
}
}
}
return result
}
But it begins to get troublesome for these reasons:
- It becomes longer
- It becomes harder to read
- It becomes harder to debug
- It becomes more sensitive to changes
- It becomes harder to test
- It becomes tiresome because you're having to think of more variable names
Instead, a recursion can be used instead which solves all of the six problems listed above:
function transformAll({ type = '', style = {}, children = [] }) {
const result = { type, style: transformStyleObject(style), children }
if (Array.isArray(result.children)) {
result.children = result.children.map(transformAll)
}
return result
}
{
"type": "div",
"style": {},
"children": [
{
"type": "div",
"style": {
"backgroundColor": "black",
"borderColor": "hotpink",
"borderWidth": "2px",
"borderStyle": "dashed",
"fontStyle": "italic",
"padding": "20px 25px",
"color": "white"
},
"children": [
{
"type": "button",
"style": {
"backgroundColor": "#fda512",
"borderColor": "red",
"color": "#ffffff"
},
"children": []
},
{
"type": "label",
"style": {
"height": "4vh",
"width": "4vw"
},
"children": [
{
"type": "label",
"style": {
"borderWidth": "5px",
"borderStyle": "solid",
"fontStyle": "italic"
},
"children": [
{
"type": "span",
"style": {
"backgroundColor": "#039392",
"borderRadius": "10px",
"height": "3vh",
"outline": "none",
"width": "78.3vw"
},
"children": []
}
]
}
]
}
]
}
]
}
Our implementation now looks a lot more elegant, and easier to read! Here's how this recursion works:
-
transformAlltakes a single object that represents an HTML DOM element. - Transforms the style attributes of that element (which is our goal for every HTML DOM element in our case)
- Checks if there are nested elements by checking the element's
childrenproperty - If there is, this function will loop through each children and re-call itself
transformAllon each child. - This starts the recursion and will loop through every object it can find through
childrenno matter how deep the tree goes.
Working With Files and Folders
I personally find it an awesome experience to write more functional code. And when there's functional code, there's more elegance. Recursion fits nicely into this.
Let's build a program that will look into every directory under a file path, scan for folders named __test__ and detect if there are any unit tests that were not implemented by looking for file names with .test.js. Each folder will be a "module", and we'll assume it doesn't have unit tests implemented for it if it either does not have a __test__ folder or does not have any files within their `test` folder that end with .test.js.
If it finds that there is a test for a module, it will return an object to us containing information about that whole directory like:
{
"../javascript-algorithms/src/algorithms/math/linked-list": {
"name": "linked-list",
"category": "algorithms",
"subcategory": "math",
"totalFiles": 0,
"filesList": []
}
}
The final result of this operation is an array of these objects, where each object represents a folder (which is a module in our case) that need our attention because they don't have unit tests yet.
Recursion can easily be used to make this happen.
I used the https://github.com/trekhleb/javascript-algorithms repo, extracted out everything inside the src directory and purposely removed a couple of unit tests in some of their examples so that our code can return those locations in our result.
The code snippets ahead imports native modules from nodejs.
First, we're going to import fs and declare a root directory to start the traversing from:
import fs from 'fs'
const rootDir = '../javascript-algorithms/src'
Next, we're going to use the isDirectory method from the fs module later to detect when to enter in directories. I personally prefer to wrap this into a function because I don't like writing the full method:
function isDirectory(filePath) {
return fs.statSync(filePath).isDirectory()
}
We're also going to create a function called hasTest that takes an array of strings, loop through them and if it finds that there is a test file then it will return true, or false otherwise:
function hasTest(testDir) {
for (let index = 0; index < testDir.length; index++) {
const filename = testDir[index]
if (filename.endsWith('.test.js')) {
return true
}
}
return false
}
Now for the main function, we'll call it findEmptyTests which is responsible for accumulating all the modules that don't have any tests implemented:
function findEmptyTests(basepath) {
let emptyTests = {}
if (isDirectory(basepath)) {
const dir = fs.readdirSync(basepath)
for (let index = 0; index < dir.length; index++) {
const filename = dir[index]
const filepath = `${basepath}/${filename}`
if (isDirectory(filepath)) {
if (filename === '__test__') {
const testDir = fs.readdirSync(filepath)
if (!hasTest(testDir)) {
emptyTests[filepath] = createMissingTestsObject(basepath, testDir)
}
} else {
emptyTests = { ...emptyTests, ...findEmptyTests(filepath) }
}
}
}
}
return emptyTests
}
We can see that this is a recursion because it calls itself at this line:
emptyTests = { ...emptyTests, ...findEmptyTests(filepath) }
Which is the most important part!
The way this function works is that we can call findEmptyTests by passing in a file path to start from.
If the file path we pass in is a directory, it will read all the files in the directory and store the file names into the dir array.
A loop is performated afterwards so that we can check which one is a directory. If it encounters a directory from the current iterating filepath, it will check two conditions:
- Is the current iterating file path the
__test__directory itself? If so, check that directory to see if there are any files ending with.test.js. If not, we grab information about that module's location in the repo. - Is the current iterating file path not a
__test__directory but is still a directory? If so, traverse inside that directory and start the whole function inside that directory, and the directory after that, etc.
Finally, the result is returned once it finished its operation.
You probably noticed the createMissingTestsObject function. It's just a function that collects information about a file path and its directory:
function createMissingTestsObject(str, dir) {
const indexToSrc = str.indexOf('src')
let category = str.substring(indexToSrc + 4)
let subcategory = category.substring(category.indexOf('/') + 1)
subcategory = subcategory.substring(0, subcategory.indexOf('/'))
category = category.substring(0, category.indexOf('/'))
return {
name: str.substring(str.lastIndexOf('/') + 1),
category,
subcategory,
totalFiles: dir.length,
filesList: dir,
}
}
This should now return us a nice object of locations that are missing unit tests!
{
"../javascript-algorithms/src/algorithms/math/fourier-transform/__test__": {
"name": "fourier-transform",
"category": "algorithms",
"subcategory": "math",
"totalFiles": 1,
"filesList": ["FourierTester.js"]
},
"../javascript-algorithms/src/algorithms/sets/cartesian-product/__test__": {
"name": "cartesian-product",
"category": "algorithms",
"subcategory": "sets",
"totalFiles": 0,
"filesList": []
},
"../javascript-algorithms/src/algorithms/sets/combination-sum/__test__": {
"name": "combination-sum",
"category": "algorithms",
"subcategory": "sets",
"totalFiles": 0,
"filesList": []
}
}
Find me on medium
Top comments (1)
I like the fact that everyone has labelled this one for future reading (like me) rather than liked it. No one can face recursion "right now"!