Learn Programming With JavaScript

A function which calls itself

A recursive function is a function which calls itself in some way. In some cases, it can be for mathematical computation like the Fibonacci sequence.

In JavaScript, the most common use case for a recursive function is for tree traversal: navigating through a data tree, all the way to the end of each branch.

Imagine the following data object as a comment on a website like Reddit:

const commentToTest = {
  content: '1',
  subComments: [
    { content: '1-A', subComments: [] },
    { content: '1-B', subComments: [
        { content: '1-B-a', subComments: [] }
    ] },
    { content: '1-C', subComments: [
        { content: '1-C-a', subComments: [
            { content: '1-C-a-i', subComments: [] },
            { content: '1-C-a-ii', subComments: [] }
        ] },
        { content: '1-C-b', subComments: [] }
    ] },
    { content: '1-D', subComments: [] }
  ] 
};

Each comment can have its own sub-comments, and each of those can have their own sub-comments etc., and you have no way of knowing in advance how many layers there will be. Let's say you want to print every single comment to the console on a separate line. In this case, a recursive function can do the trick:

const getAllComments = (comment) => {
  let allComments = comment.content;
  for (let subComment of comment.subComments) {
    allComments += '\n' + getAllComments(subComment);
  }
  return allComments;
}

In this function:

• It gets the content of whichever comment it is called on.

• If that comment has sub-comments, it calls itself for each sub-comment, adding them (on a newline '\n') to the end of its string.

• Once it has finished looping through any sub-comments, it returns the full string it has created.

For example, when you call getAllComments() on your commentToTest object:

• It sets  allComments  to  '1'

• It starts its for loop:

  • it runs a new getAllComments, passing it comment  '1-A'

    • the  '1-A' instance sets its own allComments string to '1-A'

    • there are no sub-comments, so it simply returns the string '1-A'

  • it adds a newline '\n' and the returned'1-A' string

  • it loops to the next sub-comment,  '1-B'

    • the  '1-B' instance sets its  allComments to  '1-B'

    • it starts its own for loop

      • it runs a new  getAllComments, passing it the  '1-B-a' comment

        • the '1-B-a' instance only returns  '1-B-a',  as it has no sub-comments

      • the  '1-B'  instance adds'\n' and '1-B-a' to its  allComments string

    • it no longer has any sub-comments, so returns  '1-B\n1-B-a'

  • the original call now adds this string to the end of its  allComments, making it now  '1\n1-A\n1-B\n1-B-a'

It continues like this down every branch until it has exhausted them all, and finally returns the whole string.

Let's recap!

In this chapter:

• You saw that recursive functions are functions which call themselves.

• You saw that, in the context of JavaScript, these are very often used for tree traversal — working your way through tree-like data objects.

• You saw an example of how the code works.