This is the curriculum for the 2018 Foxtrot Web Developer Bootcamp.

Recursion

Recursion is a function that calls itself until it doesn't.

Countdown from 10

Consider the following code. What do you imagine will happen when you run this code?

let countdownFrom = (num) =>{
  console.log(num)
  countdownFrom(num - 1)
}

countdownFrom(10)

If you reasoned that the process would run on and on, counting down into huge negative numbers until your computer runs out of memory, then you were correct. This is a recursive function but it has no stop condition, so it never ends. Let's add a stop condition:

let countdownFrom = (num) =>{
  console.log(num)
  if(num > 0){
    countdownFrom(num - 1)
  }
}

countdownFrom(10)

Excellent! We can now count down from 10 using recursion

What about a loop

Consider this code, which does exactly the same thing as the recursion example above:

for(let i = 10; i >= 0; --i){
  console.log(i)
}

Theoretically, what can be done with a loop can be done with recursion, but it is important to note that certain situations will favor solutions based on one implementation over the other.

Recursion and trees

Remember back to the work we did with Array.reduce(). That dataset was flat, meaning that we had an array of values, and we need to walk through each element in the array. Consider how you would handle data that was heirarchical and deeply nested, or if we needed to parse the data into a deeply nested data structure. One of the most common uses of recursion is dealing with tree like structures.

Make a Tree

We can use the filter() function built into arrays and a recursive function to create a tree structure for our data when we start off with a flat list of nodes. Consider the following dataset:

let pages = [
  {name: 'Home', parent: null, path: ''},
  {name: 'About', parent: 'Home', path: '/about'},
  {name: 'Jobs', parent: 'Home', path: '/jobs'},
  {name: 'The Olive Garden', parent: 'Jobs', path: '/the-olive-garden'},
  {name: 'The Great Dane', parent: 'Jobs', path: '/the-great-dane'},
  {name: 'Wait Staff', parent: 'The Olive Garden', path: '/wait-staff'},
  {name: 'Greeter', parent: 'The Olive Garden', path: '/greeter'},
  {name: 'Bartender', parent: 'The Great Dane', path: '/bartender'}
]

And imagine that we wanted to make a tree structure for a navigation menu, something like:

{
  "Home": {
    "url": "",
    "children": {
      "About": {
        "url": "/about",
        "children": {}
      },

      "Jobs": {
        "url": "/jobs",
        "children": {
          "The Olive Garden": {
            "url": "/jobs/the-olive-garden",
            "children": {
              "Wait Staff": {
                "url": "/jobs/the-olive-garden/wait-staff",
                "children": {}
              },
              "Greeter": {
                "url": "/jobs/the-olive-garden/greeter",
                "children": {}
              }
            }
          },
          "The Great Dane": {
            "url": "/jobs/the-great-dane",
            "children": {
              "Bartender": {
                "url": "/jobs/the-great-dane/bartender",
                "children": {}
              }
            }
          }
        }
      }
    }
  }
}

With this structure, we can have a menu that nests other menu items. How would we go about it? The answer is recursion! Here's the complete test demonstrating how to get this done:

let pages = [
  {name: 'Home', parent: null, path: ''},
  {name: 'About', parent: 'Home', path: '/about'},
  {name: 'Jobs', parent: 'Home', path: '/jobs'},
  {name: 'The Olive Garden', parent: 'Jobs', path: '/the-olive-garden'},
  {name: 'The Great Dane', parent: 'Jobs', path: '/the-great-dane'},
  {name: 'Wait Staff', parent: 'The Olive Garden', path: '/wait-staff'},
  {name: 'Greeter', parent: 'The Olive Garden', path: '/greeter'},
  {name: 'Bartender', parent: 'The Great Dane', path: '/bartender'}
]

function makeTree(pages, parent=null, url=''){
  let node = {}
  pages
    .filter( page => page.parent === parent )
    .forEach( page => {
      let fullUrl = `${url}${page.path}`
      node[page.name] = {
        url: fullUrl,
        children: makeTree(pages, page.name, fullUrl)
      }
    })
  return node
}

describe("recursion", ()=>{
  test("making trees", ()=>{
    let nodes = makeTree(pages, null)
    console.log(JSON.stringify(nodes, null, 2))
  })
})

So, what exactly are we doing in makeTree? Its recursive, lets explore a bit.

function makeTree(pages, parent=null, url=''){
  // each call to the function is going to return a node
  let node = {}

  // we pass all pages into the function each time it is run
  pages

    //filter out the pages that are children of the current node
    .filter( page => page.parent === parent )
    .forEach( page => {

      //for each child, we construct the url based on our parents url
      let fullUrl = `${url}${page.path}`

      //now we create the new node
      node[page.name] = {
        url: fullUrl,

        // and call makeTree recursivly to find all the nodes children
        // we also pass in the url, so the children can use it to build their urls.
        children: makeTree(pages, page.name, fullUrl)
      }
    })

  // finally, return node.  Its fully built!
  return node
}

Flatten a Tree

What about when you want to go the other way? You need to flatten out a nested data set. Imagine the following, oversimplification of programming languages:

languages

How would you flatten this out to an array of languages, listing the family, type, and name as attributes? You could do this with a set of nested loops, but it would be messy, and not very declarative. Its better to use recursion. Also, with recursion, if the heirarchy deepened, say to 4 levels, we could still easily handle it. With loops, it would go from bad to worse, so lets use recursion.

Here is the same data in JSON format:

let languageFamilies = {
  children: [
    {name: 'Imperative',
     type: 'family',
     children: [
      {name: 'Procedural',
       type: 'style',
       children: [
         "Ada",
         "C",
         "C++",
         "Cobol"
      ]},
      {name: 'ObjectOriented',
       type: 'style',
       children: [
         "C#",
         "Java",
         "Ruby",
         "Smalltalk"
      ]}]
    },
    {name: 'Declarative',
     type: 'family',
     children: [
      {name: 'Functional',
       type: 'style',
       children: [
         "Clojure",
         "F#",
         "Javascript",
         "Lisp",
         "Python"
      ]},
      {name: 'Logical',
       type:'style',
       children: [
         "ALF",
         "Curry",
         "Leda"
      ]}]
    },
    {name: 'Other',
     type: 'family',
     children:[
      {name: 'CauseEffectTables',
       type: 'style',
       children: [
         "XForms"
      ]},
      {name: 'SemiGraphical',
       type: 'style',
       children: [
         "Fabrik",
         "Lava",
         "Max"
      ]}]
    }
  ]
}

And we want a data structure something like so:

[
        {
          "name": "Ada",
          "family": "Imperative",
          "style": "Procedural"
        },
        {
          "name": "C",
          "family": "Imperative",
          "style": "Procedural"
        },
        ...

You probably guessed that recursion is the tool to reach for here, and you are correct!

//Our data is 3 levels deep, so as we walk the tree, we'll build up those values, passing them down to the child nodes
function flattenLanguages(node, family=null, style=null){

  //depending on what depth we're at in the tree, we need family and style values
  if(node.type === 'family'){
    family = node.name
  }else if(node.type === 'style'){
    style = node.name
  }

  //Now for the recursive part, we need to drill down into child nodes
  if(node.children){

    //reduce is the right tool here because we need to build up one long array of all returned child nodes
    return node.children.reduce( (nodes, child) => {
      //concat joins two arrays into one new array
      return nodes.concat(flattenLanguages(child, family, style))
    },[])
  } else {
    //no children, so we must be at the language level, return the node wrapped in an array, so it can be concated above
    return [{name: node, family: family, style: style}]
  }
}

describe("tree manipulation", ()=>{
  test("should flatten tree", ()=>{
    let languages = flattenLanguages(languageFamilies)
    console.log(JSON.stringify(languages, null, 2))
    expect(languages.length).toBe(20)
  })
})

Challenges

  • Considering the family tree, refactor the starting data so each child has an array of parents. How would you modify the recursive function to handle this?
  • Considering the programming language tree, refactor the data so that each language is a node, and contains an array of versions. Update the recursive function to parse this data into an array with the following format:
[
  {family: 'Imperative', style: 'Procedural', language: 'C', version: '1.2'},
  {family: 'Imperative', style: 'Procedural', language: 'C', version: '1.2'}
]

Currying

Currying a function means building a function in a way that it returns another function until all the arguments have been passed into it, and it returns the final result.

Wait what?

First an example

First, lets look at an example of a curried function, and then we'll talk more about why this is a useful functional programming technique.

let vacationPlanner = when =>
  where =>
    withWho =>
      `${when} I'm taking a trip to ${where} with ${withWho}.`

describe("currying", ()=>{
  it("should return a string", ()=>{
    let result = vacationPlanner("Tomorrow")("Hawaii")("my family")
    expect(result).toBe("Tomorrow I'm taking a trip to Hawaii with my family.")
  })
})

Notice what is going on here.

let result = vacationPlanner("Tomorrow")("Hawaii")("my family")

First we call vacationPlanner("Tomorrow") and it returns a function that expects a place ("Hawaii") as its argument, then we call that function with another argument of who we're traveling with, "my family". When we call it for that third and final time, the function responds with a string.

What is currying good for

So, currying is nothing new, except for the pattern of returning a series of functions until it can return the result that is useful, but wy would we ever want to do this? Seems complicated. The answer lies in the complexity of a real world application. Imagine that you wanted to search a list of cities by Mayor.

Without Currying

First, lets solve our search problem without using currying. Here's the data we'll be searching:

let cities = [
  {name: 'San Diego', mayor: 'Kevin Faulconer'},
  {name: 'Los Angeles', mayor: 'Eric Garcetti'},
  {name: 'San Francisco', mayor: 'Ed Lee'}
]

And without using Currying, we could do this search like so:

let hasMayor = (mayor, city)=>{
  return city.mayor === mayor
}

let mayorSearch = (searchTerm) => {
  //Iterate over each city, and check for a match
  return cities.filter(city => hasMayor(searchTerm, city))
}

//then, running the search
mayorSearch("Kevin Faulconer")

That works, but this line in particular feels clumsly and is not flexible:

return cities.filter(city => hasMayor(searchTerm, city))

Using Currying

So, how can we improve this with currying?

let hasMayor = (mayor) => {
  return (city) => {
    return city.mayor === mayor
  }
}

let mayorSearch = (searchTerm) => {
  //Much cleaner!
  //hasMayor() returns a function the first time,
  //which is exactly what filter() takes as an argument
  return cities.filter(hasMayor(searchTerm))
}

Challenges

  • Write a curried function to search by city name
  • Refactor the recursive example for parsing tree data to use currying.