Practical introduction to Functional Programming with JS

AndreaZanin
4,064 views

Open Source Your Knowledge, Become a Contributor

Technology knowledge has to be shared and made accessible for free. Join the movement.

Create Content

Recursion

A recursive function is a function that calls itself until it hits a base case. This is often used in recursive languages as a replacement for loops, because it is far more flexible. They key here is that each time the function calls itself, the problem is reduced.

Just to understand the concept, let's implement a countdown as a recursive function:

Countdown
1
2
3
4
5
6
7
8
9
10
11
let countdown = (num) => {
if (num === 0) { // base case
console.log("BOOM");
}
else {
console.log(num);
countdown(num-1); // recursive call on a reduced problem: num-1
}
}
countdown(5);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Recursion is much more powerful than loops; for example, they are very useful to implement any algorithm of the "divide and conquer" family. We'll implement a simple algorithm that tells us whether a file is in a directory or in sub-directories.

Finding a file
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
OUR FILESYSTEM IS THIS
home
├── andrea
·· ├── funds.csv
·· └── paper.pdf
├── john
·· ├── logs
···· ├── logs1
···· ├── logs2
···· ├── logs3
···· └── logs4
·· ├── summer1.jpg
·· ├── summer2.jpg
·· └── summer3.jpg
├── notes.txt
└── todo.txt
*/
const tree = {
name : "home",
files : ["notes.txt","todo.txt"],
subFolders: [{
name : "andrea",
files : ["paper.pdf","funds.csv"],
subFolders: []
},
{
name: "john",
files : ["summer1.jpg","summer2.jpg", "summer3.jpg"],
subFolders: [{
name : "logs",
files : ["logs1","logs2","logs3","logs4"],
subFolders: []
}]
}]
};
find = element =>
tree =>
{
if (tree.files.indexOf(element)!==-1){ // that is if the element is in this folder
return true;
}
else if (tree.subFolders.length !== 0){ // that is if the are subfolders
const otherFolders = tree.subFolders.map(find(element)); // searches the element in every subfolder
const aOrB = (a,b)=>a || b; // a function applying the or operator
const found = otherFolders.reduce(aOrB, false); // returns true if element was in at least one of the subfolders
return found;
}else{
return false; // returns false if it's not in this folder and there are no subfolders
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

In this tiny example, we used recursion, currying, higher order function and lambda expressions, which is nice per se, but most importantly, we solved a problem that is unsolvable using only loops.

And now an exercise for you: from a list of {id,parent} objects you have to create the original structure. You can assume that every object has a unique id.
E.g. this list

[
  { "id": "Grandad", "parent": null },
  { "id": "Dad", "parent": "Grandad" },
  { "id": "You", "parent": "Dad" },
  { "id": "Son", "parent": "You" },
  { "id": "Daughter", "parent": "You" },
  { "id": "Brother", "parent": "Dad" },
  { "id": "Nephew", "parent": "Brother" },
  { "id": "Niece", "parent": "Brother" },
  { "id": "Sister", "parent": "Dad" },
  { "id": "Uncle", "parent": "Grandad" },
  { "id": "Cousin", "parent": "Uncle" }
]

should become this

"Grandad": {
  "Dad": {
    "You": {
      "Son": {},
      "Daughter": {}
    },
    "Brother": {
      "Nephew": {},
      "Niece": {}
    },
    "Sister": {}
  },
  "Uncle": {
    "Cousin": {}
  }
}
}

Hint: the subtrees are smaller versions of the treeBuilding problem, can you figure out what the base case is?

Finding a file
1
2
3
4
5
const buildTree = (list, parent) => // parent is the root of the tree/subtree
// TODO
// {...}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

As this problem is harder that usual I provided the solution here

Open Source Your Knowledge: become a Contributor and help others learn. Create New Content