Maya Gans

I’ve gotten pretty far in the past year and a half or so of my limited JavaScript knowledge, but I still have some glaring gaps that I’d like to address. My familiarity with recursive functions ends after the classic Fibonacci sequence or counter example. I found myself asking okay but when am I actually going to use this? There must be a time were recursion will shine and I can’t just brute force my way through with a for loop…. right?

Hierarchical Data!

Enter hierarchical data. Let’s say you have hierarchical data represented in a flat structure. Here we have elements with an id, that each have a parent element. At the highest level we have body which doesn’t have a parent element, but both hand and foot have the body parent. Then finger has the parent hand and toe the parent foot. Let’s structure this data as a tree to represent these relationships better!

let anatomy = [
 { id: 'body',   parent: null },
 { id: 'hand',   parent: 'body' },
 { id: 'ring finger', parent: 'hand' },
 { id: 'pinky', parent: 'hand' },
 { id: 'foot',   parent: 'body' },
 { id: 'big toe',    parent: 'foot' }
]

The recursive function

The logic behind our recursive function is that we need a function that will filter for each unique parent, then look for all the id’s that share that parent. Then the recursive function calls itself in order to make those id’s the next level’s parents:

let makeTree = (categories, parent) => {
  // create a variable we can manipulate
  let node = {}
  
  categories
     // get the root parent (supplied in function as arg)
    .filter(c => c.parent === parent)
     // get all the ids with the specified parent
    .forEach(c => node[c.id] = 
      // now make this same tree, 
      // but here we use the current id as the parent
      makeTree(categories, c.id))
  // the variable we manipulate is our output
  return node
}

console.log(JSON.stringify(makeTree(anatomy, null)), null, 2)

{
  body: {
    hand: {
      "ring finger": {},
      "pinky":{}
    },
    foot: {
      "big toe": {}
    }
  }
}

In the first loop, we pass in our object, anatomy and also pass in the root parent: null. For every body part we use forEach to assign the node (body) and give it the return value of the same function, but this time we’re not passing in anatomy, we’ve passed in body so it will return hand and foot - and we recurse down assigning all fingers to hand and toes to feet. This recursion happens all the way down until there are not properties left to assign.

This tree structure makes it quite obvious that body contains both hand and foot, which contains finger and toe respectively. A little more practical than the Fibonacci sequence example if you ask me…

Translating into R:

I wanted to translate this function into #rstats and of course Twitter came through. With the help of Jakub T. Jankiewicz we can translate this function above into #rstats using applys!

Given this list of lists:

anatomy <- list(
  list(id = 'body', parent = NULL),
  list(id = 'hand', parent = 'body'),
  list(id = 'ring finger', parent = 'hand'),
  list(id = 'pinky', parent = 'hand'),
  list(id = 'foot', parent = 'body'),
  list(id = 'big toe', parent = 'foot')
)

We can make our recursive function

We can create an empty list and filter it based on the selected parent argument. We use this same argument and assign it as the node id, then run the makeTree function on that node again, going deeper and deeper into the tree

makeTree <- function(categories, parent) {
  node <- list()
  filtered <- sapply(categories, function(c) {
    identical(c$parent, parent)
  })
  lapply(categories[filtered], function(c) {
    node[[c$id]] <<- makeTree(categories, c$id)
  })
  node
}

makeTree(anatomy, NULL)

$body
$body$hand
$body$hand$`ring finger`
list()

$body$hand$pinky
list()


$body$foot
$body$foot$`big toe`
list()