@tesla809/

recursion - fp - Fun Fun Function

JavaScript

Notes on recursion from Fun Fun Function's series on functional programing.

fork
loading
main.js
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// from fun fun function
// recursion - Part 7 of Functional Programming in JavaScript
// https://www.youtube.com/watch?v=k7-N8R0-KY4

// functional programming - the process of building software by composing pure functions, avoiding shared state, mutable data, and side-effects. You can avoid lots of bugs this way.

// recursion- when a function calls itself untill it doesn't

// need termination condition if not will count forever or until the maximum call stack is exceeded.
// call stack- is the stack of function calls that your code has made
// in most nonfunctional programming languages there is an upper limit to how far you can call functions.
// functional programming languages don't have this limit because they use recursion for everything!
// JavaScript has this limiation in ECMAScript5, but removed in ECMAScript6, aka es6, even though babel can't simulate it due to its engine.
// This feature is called tail call optimization, and it removes one of the main impediments to doing functional programming in javascript. Its called that because its a big tail of function calls.

// to avoid the maximum call stack error and get an answer, we need a stop condition.

// will output countdown.
// implicitly assumes num to return.
let countDownFrom = num => {
  if(num === 0) return;
  console.log(num);
  countDownFrom(num - 1);
}

countDownFrom(10);

// why would we want recrursion
// Everytime we do a loop, we could use recursion instead.
// However, there aren't things that recursions can do that loops cannot.

// Good use of recursion
// Top category animals had no parent category.
// Hierarchy of categories

// we wanted to represent this database into something like directory, where directories nest into other directories if they are sub categories.
// dogs and cats folders into the mammals folder. Mammels into the animals folder, etc. 
// Recursion is good for that.

let categories = [
  { id: 'animals', 'parent': null },
  { id: 'mammals', 'parent': 'animals' },
  { id: 'cats', 'parent': 'mammals' },
  { id: 'dogs', 'parent': 'mammals' },
  { id: 'chihuahua', 'parent': 'dogs' },
  { id: 'labrador', 'parent': 'dogs' },
  { id: 'persian', 'parent': 'cats' },
  { id: 'siamese', 'parent': 'cats' },
];

let makeTree = (categories, parent) => {
  let node = {};  // create new node
  categories
    // find root by finding node with no parent in first pass
    // filter out ones that have same parent as passed in
    .filter(c => c.parent === parent) 
    .forEach(c => 
    // assign property of node with next makeTree call
    // this time we pass in c.id as the parent (since it is)
    node[c.id] = makeTree(categories, c.id));  
  return node;
}

// Note the association between .parent and .id
// They match and where they match is the Hierarchical relation.

// Explaination
// So animal has a parent of null.
// All animal types are returned, which is one element
// we pass animal to the next function
// then make animal a node of the node object.
// Then we call makeTree and assign it to the node
// to link them, thus repeating the process
// This time we pass in the current node, animal as the parent.
// This process happens again with untill we run out of nodes.

// recursion is better than loops for large amounts of nesting
// You could do this with nested for loops
// but it will look too complicated.
// This only works with limited amount of nesting
// Recursion works with large amounts of nesting

console.log(
  // formats objects to nice viewable style
  JSON.stringify(
    makeTree(categories, null)
    , null, 2)
)


// A tree structure.
/*
end goal for task:
{
  animals: {
    mammals: {
      dogs: {
        chihuahua: null,
        labrador: null,
      },
      cats: {
        persian: null,
        siamese: null,
      }
    }
  }
}
*/

Native Browser JavaScript