Introduction

Recursive thinking is one of the crazy rides in the DSA journey. Beyond just figuring out the base and recursive cases, the mechanics easily gets out of control, making it challenging to trace the flow properly. Whereas loops may, in some cases, be more applicable, recursion beats the game with elegance (although, with memory and speed trade-offs)

Moreover, there are problems that are just too difficult or even impossible to solve without recursion. Think of a social media comment section like reddit or twitter, where you can reply to a comment, and then someone else can reply to your reply, and so on. This is a classic example of a Nested Comments System (NCS). The depth of the nesting is not known beforehand and can go deeper on many lower levels. This is a perfect use case for recursion.

Note that this post is not to teach you about recursion.

Hence, to feel comfortable following through to the end, you must fit the following profile.

You know the basics of recursion and have solved a few simple questions around it
You have some knowledge of trees and how to perform a Depth-First Search/Traversal (DFS)
You know basic React and Typescript (states, props, map, filter)

Here is a live link to the final version of the app. This post doesn't highlight anything about styling, layout and other aesthetics you might see in the final version. The full code is hosted on this github repo for your perusal.

Find below the roadmap!

Goals
PART 1 : Foundational Logic
A simple recursive function
Depth-First-Search/Traversal
PART 2: Building the APP
Extending the Comment Interface
Rendering a single comment using CommentBlock.tsx
Rendering all comments to the screen using CommentThread.tsx
Adding a comment to the tree
Deleting a comment
Drawbacks and Trade-offs
Conclusion
Credits and Acknowledgements

Goals

My goal for this post in not to spoon-feed you with code that you can plug into your app (chatGPT can help you with that or the github repo), but to breakdown the mechanics of the behavior of a NCS so that you understand what is happening on a deeper level. Ultimately, you should be able to recreate the logic and customize it to fit your needs. Also, its a future time-saver for me because I have a really terrible memory and these technical articles I write come in handy whenever I need a refresher.

We will do this in 2 steps.

Build out the foundational logic for the behavior of the NCS using textbook/classroom knowledge
Build the setup and the basic ReactJS components needed to get the app functional.

PART 1 : Foundational Logic

A simple recursive function

This function is going to be a foundational reference point and a low-level template for how a NCS would behave. It takes a positive integer as input, then it prints the integer and all other positive integers less than the input. Let's call it printNumLadder

printNumberLadder.ts

/**
 * Prints a positive integer and all other positive integers less than it
 *
 * @param {num} - the input positive integer
 *
 * @return null
*/
function printNumLadder(num: number) {
  // base case
  if (num <= 0) return

  console.log(num)

  // recursive case
  printNumLadder(num - 1)
}

printNumLadder(3);

Result

The recursive flow of this function mimics the behavior of a NCS -- We render a parent comment, then proceed to render all the sub comments in it by recursively calling its sub-comments till there are none.

The Base Case, if num <= 0 is linguistically similar to if there are no more sub comments...

The Recursive Case pNL(num - 1) is similar to call the next comment below this one

Translating the previous code to reflect a NCS, we have..

logComment.ts

interface Comment {
  text: string
  child: Comment | null
}

function logComment(comment: Comment) {
  /**
   * BASE CASE
   * stop if there are no more comments
  */
  if (comment === null) return

  // print the current comment text
  console.log(comment.text)

  /**
   * RECURSIVE CASE
   * call the next child comment of the current comment
  */
  logComment(comment.child)
}

However, the above setup doesn't work. It makes sense if there is just one parent comment that has a single child comment, which in turn has a single child comment and so on.

But NO! In reality, there are multiple comments. Each comment has a number of children (replies). Each child (reply) has its own children and so on. Therefore we have a TREE! And how do we traverse trees recursively? You are right! Depth-First Search/Traversal (DFS).

Depth-First-Search/Traversal

Now that we are aware that we are dealing with a tree, we know we need to traverse recursively in a depth-first fashion to perform any modifications on the Comment Tree. So, let's modify the logComment function to do just that

Before that, here are some key reminders to note.

The main components of a comment we will focus on are text and children/sub comments. The sub comments or children are what we linguistically call Replies. But lets call them children for the sake of technicality.

interface Comment {
  text: string | null
  children: Comment[] | null
}

For comments sections on social media, there isnt a starting root comment from which all others branch out. Its rather a list of independent Top-Level comments written by different users. Its from these Top-Level comments that other users may choose to reply to.

So, there is literally no ROOT. But we can create an imaginary/fake root comment. This imaginary/fake root will have no text, but its children will be the Top-Level comments if there are any. This makes it possible to pass a ROOT to initiate the recursive chain.

Displaying Comments

logCommentWithDFS.ts


function logCommentWithDFS(comment: Comment) {
  // base case
  if (!comment) return

  console.log(comment.text)

  // recursive case with DFS
  for (let i = 0; i < comment.children.length; i++) {
    logCommentWithDFS(comment.children[i])
  }
}

Adding Comments To Comment Tree

To add a comment to the tree, we need to know exactly where to attach it. A comment can either be a top-level comment or a sub-comment (reply).

For sub-comments, we need to know the id of the parent comment they belong to. By performing DFS, we are able to go lower levels to find that parent and then attach the sub-comment.

Top level Comments dont have parents; they are right at the top level and there is no need to go any levels below to attach them. Hence, we can add them directly to the children of the imaginary/fake root.

addCommentWithDFS.ts

const fakeRoot = {
  text: null,
  children: [] // will contain top-level comments
}

/**
 * Inserts a comment at the appropriate node in the comment tree
 *
 * @param {commentRoot} - the root of the comment tree
 * @param {parentId} - the id of the parent to which the comment belongs
 * @param {commentText} - the comment's text content
 *
*/
function addCommentWithDFS(
    commentRoot: Comment | null,
    parentId: string | null,
    commentText: string
  ) {

  // base case
  if (!commentRoot) return

  // inserting a top-level comment
  if(parentId === null){
    commentRoot.children.push({
      text: commentText,
      children: []
    })
    return;
  }

  // recursive case with DFS to attach sub-comments (replies)
  for (let i = 0; i < commentRoot.children.length; i++) {
    const currComment = commentRoot.children[i];

    if(currComment.id === parentId){
      currComment.children.push({
        text: commentText,
        children: []
      })
      return;
    }

    addCommentWithDFS(currComment, parentId, commentText)

  }
}

Deleting Comments From The Comment Tree

To delete a comment, we need to know is its id and its parent's id.

Then perform DFS to find the parent, after which we loop through its children to filter out the target child.

Remember also that Top-Level Comments dont have parents and so should be treated differently like we did previously.

deleteCommentWithDFS.tsx


function deleteCommentWithDFS(
  commentRoot: Comment | null,
  parentId: string | null,
  commentId: string
){

  if(commentRoot === null) return;

  // For Top-Level Comments
  if(parentId === null){
    commentRoot.children = commentRoot.children.filter((child: Comment) => {
      return child.id != commentId
    })
    return;
  }

  // recursive case with DFS to delete sub-comments (replies)
  for (let i = 0; i < commentRoot.children.length; i++) {
    const currComment = commentRoot.children[i];

    if(currComment.id === parentId){
      currComment.children = currComment.children.filter((child: Comment) => {
        return child.id != commentId
      })
      return;
    }

    deleteCommentWithDFS(currComment, parentId, commentId)
  }
}

We did it! All we need to do now is replicate the logic using a frontend framework of our choice. For me, ReactJS is that guy!

PART 2: Building the APP

Below is a visual representation of the app. Starting from innermost component CommentBlock.tsx, I will explain what happens at each level.

In order not to clutter each section, we will focus on the code needed only for that section. Then we can put all together in the end. But keep in mind that the sections are connected and what happens in a previous section is connected to the next and may even use code from previous sections.

Secondly, javascript events like onChange or onClick for passing data around or triggering functions will not be demonstrated. We will assume that these events have been triggerd and all we need is to call the function being called in response to those events.

Extending the Comment Interface

Let's extend the previous Comment interface to include id and user and dates.

interface User {
  id: string
  name: string
  profileImg: string
}

interface Comment {
  id: string
  text: string
  user: User
  replies: Comment[]
  createdAt: Date
}

Rendering a single comment using CommentBlock.tsx

The CommentBlock component is the visual representation of a single comment. It is what users would see and interact with. It takes a comment data as an input prop and renders it on the screen.

Additionally, this component will recursively render any replies/sub-comments for the current comment.

CommentBlock.tsx


export default function CommentBlock({comment}){
  return (
    <div>
      <p>{comment.text}</p>
      <div>
        <button>reply</button>
        <button>delete</button>
      </div>

      {/**Recursive rendering of comment replies*/}
      {
        comment.replies.length > 0 && comment.replies.map(
          (reply: Comment) => <CommentBlock comment={reply}/>
        )
      }
    </div>
  )
}

Rendering all comments to the screen using CommentThread.tsx

This component will take an array of all the comments, loop through and render them to the screen by passing each comment's data to CommentBlock

By looping through and passing each comment's data to CommentBlock, it starts the recursive chain that results in the rendering of sub comments for each top-level comment.

CommentThread.tsx

export default function CommentThread({allComments}) {
    return allComments.map(
      (comment: Comment) => {
          return <CommentBlock key={comment.id} comment={comment}/>
      }
    )
  }
}

Finally, **CommentSection.tsx** encloses everything. It is also where state is defined and pass down as props to CommentThread and CommentBlock.

CommentSection.tsx

export default function CommentSection(){

  const [allComments, setAllComments] = useState<Comment[]>(dummyCommentData); // dummyCommentData is an array of comments
  const [currentUser, setCurrentUser] = useState<User[]>(dummyCurrentUser); // dummyCurrentUser is the current user

  return <CommentThread
            allComments={allComments}
            setAllComments={setAllComments}
            currentUser={currentUser}
          />
}

Adding a comment to the tree

To perform any modifications to the comment tree, you guessed it -- we will use setAllComments set state action defined in CommentSection.tsx

Its important to remember that adding a comment to the tree will be in 2 ways. Either as a **Top-Level comment** or as a **sub-comment/reply** to a parent comment. Hence, the way in which we use **setAllComments** to modify the state will be different.

1. Adding a comment as top-level



/**
 * Creates a new comment object
 *
 * @param {commentText} - the text of the new comment
 * @param {currentUser} - the user adding the comment
*/

function newComment(commentText: string, currentUser: User){
  return {
    id: String(Math.random()), // NB: not the best way to generate ids; use uuid instead or a backend
    text: commentText,
    user: currentUser
    replies: []
    createdAt: new Date()
  }
}

/**
 * Adds a comment at the top level
 *
 * @param {commentText} - the text of the new comment
 * @param {currentUser} - the user adding the comment
 */

function addTopLevelComment(commentText, currentUser){
  setAllComments((prevComments) => {
    return [newComment(commentText, currentUser), ...prevComments.]
  }
  )
}

2. Adding a comment as a child(reply)

For this, we need to know exactly where to insert the comment like we deduced before in the Part 1 of this post. What do we need to know? The id of the parent comment to which we are attaching the reply.

Secondly, we need to perform DFS to find it since it will be deep down the comment tree.

/**
 * adds a reply to a parent comment
 *
 * @param {commentText} - the text of the new comment reply
 * @param {parentId} - the id of the parent comment to which the reply is added to
*/
function addReply(commentText: string, parentId:string){
  // allComments and setAllComments are already defined with useState in CommentSection.tsx
  const commensWithReplies = [...allComments]
  addNestedCommentDFS(commentsWithReplies, commentText, parentId)
  setAllComments(commentsWithReplies)
}

/**
 * performs DFS on a comment subtree to update its children
 *
 * @param {commentsWithReplies} - the comment subtree
 * @param commentText - the text of the new comment to be added as a child
 * @param {parentId} - the parent comment to search for
*/

function addNestedCommentDFS(
  commentsWithReplies:Comment[],
  commentText: string,
  parentId:string
  ) {

  for (let i = 0; i < commentsWithReplies.length; i++){
    const comment = commentsWithReplies[i]

    if(comment.id === parentId){
      comment.replies [
        newComment(commentText, currentUser),
        ...comment.replies
      ]
    }else{
      addNestedComment(comment.replies, commentText, parentId)
    }
  }

}

Deleting a comment

Again, from Part 1, we figured out that we needed to know the comment's id and its parent's id. If it has no parent, then its a top level comment, other wise its a nested comment reply.

NB: Deleting a comment automatically deletes its chldren as well

1. Deleting a top level comment

/**
 * Deletes a comment at the top level
 *
 * @param {commentId} - the id of the comment to be deleted
 */
function deleteTopLevelComment(commentId: string) {
  setAllComments((prevComments: Comment[]) =>
    prevComments.filter((comment: Comment) => comment.id != commentId)
  )
}

2. Deleting a nested comment/reply

function deleteReply(commentId: string, parentId: string) {
  const commentsWithReplies = [...allComments]
  deleteNestedCommentDFS(commentsWithReplies, commentId, parentId)
  setAllComments(commentsWithReplies)
}

function deleteNestedCommentDFS(
  commentsWithReplies: Comment[],
  commentId: string,
  parentId: string
) {
  for (let i = 0; i < commentsWithReplies.length; i++) {
    const comment = commentsWithReplies[i]

    if (comment.id === parentId) {
      comment.replies = comment.replies.filter((comment) => comment.id !== commentId)
    } else {
      deleteNestedCommentDFS(comment.replies, commentId, parentId)
    }
  }
}

Drawbacks and Trade-offs

Just because you can solve it recursively doesn't mean you should! If there is an iterative solution that is more efficient, then you should use that instead.

Here are some of the common issues with recursion.

Stack Overflow - If the depth of the tree is too large, the recursive function will keep calling itself until the stack overflows, causing your app to crash.
Performance Overhead - The larger the tree, the more function calls are going to be made and the more memory is going to be used. Overall, your app will be slower.
Debugging - Debugging recursive functions can be a nightmare. It's easy to get lost in the recursive calls and lose track of what's happening. Even more crazy is when there are multiple base and recursive cases.

Using recursion in production should be done with caution. It's not always the best solution, but when it is, it's a beautiful thing.

Conclusion

This has been a fun ride for me. From diagramming, editting, debugging, coding, testing and to the final version of this post. There is many more ideas currently in development and if you loved this, you should consider subsribing down below. Your comments and feedback are welcome as well.

Here are some interesting things you can include on your own.

Connect to a database to persist the comments.
Include Web sockets for realtime comment updates from different users
Trigger notifications when comments are added.

Credits and Acknowledgements

Shoutouts to these gurus for making this write-up better with their feedback and suggestions.

David Quarshie
Abdul Sabit Ariff
Assan Ewudzi Nathaniel

Thanks.ts

console.log('Thanks for reading');

Subscribe to the newsletter