Recursion used to be one of those topics that'd scare me when I first started out coding. To be honest even after all this years I still struggle sometimes. However, the only difference today compare to back when I started coding is I am no longer intimidated when I encounter recursion.
Reading through a lot of code and diving deep into it helped me prepare a mental model. In fact after gradually grasping how recursion works, it opened a whole new dimension to problem solving.
Concepts like tree, graph, trie, traversal started making sense to me.
Taking inspiration from the learnings and also since I am on a job hunt 😛. I randomly decided to challenge my self if I can create a directory structure given a JSON input, if I can solve it within a stipulate amount of time if asked in an interview.
Although I took extra bit of time than what I'd assigned for the problem, I was thrilled to see it work. The joy was same as getting hello world printed the first time in your coding journey.
For those of you who still find recursion difficult to grasp, I'll try to explain the concept with a simple analogy.
The analogy assumes that you are a part of a imaginary family and you are the eldest of all 4 siblings.
Let's say the head of the family i.e, your father/mother 👪 orders you to fetch groceries (the most exciting job after coding). Now you can't straight away reject if you don't feel like doing it. You being the eldest one have some responsibility.
The younger one's look up to you and try to emulate your personality. Since, your siblings are looking up to you, you feel powerful and with great power comes the power to delegate boring tasks to your next in line sibling.
The next in line sibling in turn feels entitled to power just by the virtue of being the eldest amongst the rest. So he/she does what he/she saw and tries to emulate the same behaviour.
This behaviour is repeated until the youngest one, who is aimlessly wandering looking for answers to life, universe and everything, is assigned the task of fetching groceries and for some reason he/she seems to be exited about it.
The all obeying youngest sibling fetches the groceries and returns it along with the total bill amount of 42 to the elder one just after him/her. The next in line elder sibling does the same thing, taking the credit for himself of course as they always do. This pattern of returning the groceries continues until it reaches head of the family.
Here's how the delegation tree looks like while requesting groceries.
👪 (Fetch some groceries 🥦🥒🍅, I'll wait)
↓
🧑🏼 (Fetch some groceries 🥦🥒🍅. I'll wait)
↓
👦🏽 (Fetch some groceries 🥦🥒🍅. I'll wait)
↓
🧒🏻 (Fetch some groceries 🥦🥒🍅. I'll wait)
↓
👦🏽 (Fetch some groceries 🥦🥒🍅. I'll wait)
↓
👶🏼 (Fetch some... oh wait I am the youngest one... here's the grocery 🥦🥒🍅. I am done)
Here's how the delegation tree looks like while returning groceries.
👶🏼 (here's the grocery 🥦🥒🍅. I am done)
↓
👦🏽 (Here's the grocery 🥦🥒🍅. I am done)
↓
🧒🏻 (Here's the grocery 🥦🥒🍅. I am done)
↓
👦🏽 (Here's the grocery 🥦🥒🍅. I am done)
↓
🧑🏼 (Here's the grocery 🥦🥒🍅... I am so exhausted.)
↓
👪 (groceries 🥦🥒🍅.)
Sudo code for above recursion
const fetchGroceries = (elder) => {
if (elder.next === null) return {text: "groceries": bill: 42}
return fetchGroceries(elder.next)
}
fetchGroceries(elder)
The above to and fro between the caller and the callee is the crux of recursion functions. It nothing but a bunch of function pushed on to the call stack each in turn pushing other functions to call stack...staying on the call stack until the function they called returns. Each called function after returning pops itself off the call stack.
Let's have a look at slightly more complex analogy, where the annual salary of the CEO is 1 + salary of all employee who are employed under him/her.
Here's how the tree would span out while being called
👩🏼💼 (I make 1 + whatever my junior make)
/ \
(I make 1 + whatever my junior make) 👨🏼💼 👨🏻💼 (I make 1 + whatever my junior make)
/ \
(I make 1 + whatever my junior make)👨🏼💼 👨🏻💼 (I make 1 + whatever my junior make)
/ \ \
/ \ 👨🏻💼 (Don't have a junior, I make 1)
/ \
/ \
/ \
/ \
(No junior, I make 1) 👨🏼💼 👨🏼💼 (I make 1 + whatever my junior make)
\
👨🏼💼 (Don't have a junior, I make 1)
Here's how the tree would shrink while function calls are returned
👨🏼💼 (I make 1, 1 + 0 from my junior)
(I make 1, 1 + 0 from junior)👨🏼💼 /
\ 👨🏼💼 (I made 2, 1 + 1 from my junior)
\ /
\ /
\ /
\ /
\ / 👨🏼💼 (I make 1, 1 + 0 from junior)
\ / /
\ / 👨🏼💼 (I make 2, 1 + 1 from my junior)
(I make 4, 1 + 3 from junior)👨🏼💼 /
\ 👨🏼💼 (I make 3, 1 + 2 from my juniors)
(I make 5, 1 + 4 from juniors)👨🏼💼 /
\ /
(I make 6, 1 + 5 from junior)👨🏼💼 /
\ /
\ /
\/
👩🏼💼 (I make 10, 1 + 9 from junior)
sudo code for above recursion
const ceoPay = (ceo) => {
if (ceo == null) return 0;
leftJuniorPay = ceoPay(ceo.left)
rightJuniorPay = ceoPay(ceo.right)
return 1 + leftJuniorPay + rightJuniorPay
}
ceoPay(root)
Congratulations, you just learned how to calculate number of nodes in a binary tree.
You can carry forward what you have learned and extend it to create a directory structure. Have a look at the jsbin example below to get an idea.
👉🏻 jsbin
const directoryRoot = [
{
type: "folder",
name: "root",
path: "/root",
children: [
{
type: "folder",
name: "Downloads",
path: "/downloads",
children: [{
type: "file",
name: "movie.mp4",
path: "/movie",
children: []
}]
},
{
type: "folder",
name: "Documents",
path: "/documents",
children: [{
type: "folder",
name: "app",
path: "/app",
children: [{
type: "file",
name: "index.html",
path: "/index.html",
children:[]
},{
type: "folder",
name: "src",
path: "/src",
children:[{
type: "file",
name: "index.js",
path: "/index.js",
children:[]
}]
}]
}]
},
{
type:"folder",
"name":"Pictures",
"path":"/pictures",
children:[{
type:"file",
"name":"2018-09-12.jpg",
"path":"/2018-09-12.jpg",
"children": []
},{
type:"file",
"name":"2020-19-03.jpg",
"path":"/2020-19-03.jpg",
"children": []
}]
},
{
type:"folder",
"name":"Music",
"path":"/music",
children:[{
type:"folder",
"name":"hiphop",
"path":"/hiphop",
"children": [{
type:"file",
"name":"music-hiphop.mp3",
"path":"/music-hiphop.mp3",
"children": []
}]
},{
type:"folder",
"name":"classical",
"path":"/classical",
"children": [{
"type":"file",
"name":"music-classical-1.mp3",
"path":"/music-classical-1.mp3",
"children": []
}, {
"type":"file",
"name":"music-classical-2.mp3",
"path":"/music-classical-2.mp3",
"children": []
}, {
"type":"file",
"name":"music-classical-3.mp3",
"path":"/music-classical-3.mp3",
"children": []
}]
},{
type:"folder",
"name":"desi",
"path":"/desi",
"children": [{
"type":"file",
"name":"music-desi-1.mp3",
"path":"/music-desi-1.mp3",
"children": []
}]
}]
}
],
},
];
const recursive = function(dir, index) {
let str=" ".repeat(index) + "├── " + dir.name
index+=4
str+=`
`
for (const folder of dir.children) {
str+=constructDirectory(folder, index)
}
return str
}
const constructDirectory = function (root, index) {
if (root && root.type == "file") {
return " ".repeat(index) + "├──" + root.name+'\n\t'
}
return recursive(root, index)
};
console.log(constructDirectory(directoryRoot.pop(), 0));
Top comments (0)