What Is Recursion, and When Is It Useful?

In computer science, recursion is a key programming technique in which a function calls itself one or more times until a specific condition is met. It can be particularly useful when working with deeply nested structures that prove too complex for an iterative solution.

Though recursion seldom appears in an average programmer's day-to-day work, there are real-world use cases in frontend web applications, like the one we'll go over here.

A Practical Use for Recursion in React

My team was tasked with putting together a reusable, infinitely nested tree component. The nested data structure coupled with infinite depth presented an opportunity for a recursive approach. Follow along to understand the ins and outs of a working React Tree component powered by recursion + React rendering.

Giving our component nested data in the following shape, we’ll now have a functioning, modular, and recursive component ready for use!

interface TreeBranch {
  readonly id: string
  readonly label: string
  branches?: Tree
  readonly selected?: boolean
}

type Tree = ReadonlyArray<TreeBranch>

const mockOrgTreeList: Tree = [
  {
    label: "Liberty Health",
    id: "1",
    branches: [
      {
        label: "Pacific Northwest",
        id: "2",
        branches: [
          {
            label: "East Portland Clinic",
            id: "3",
            branches: [],
          },
          {
            label: "Beaverton / Tigard",
            id: "4",
            branches: [],
          },
          {
            label: "Lake Oswego Regency",
            id: "5",
            branches: [],
          },
        ],
      },
      {
        label: "Alaska",
        id: "6",
        branches: [],
      },
    ],
  },
  {
    label: "Northstar Alliance",
    id: "7",
    branches: [
      {
        label: "Chicago",
        id: "8",
        branches: [
          {
            label: "Southwest Region",
            id: "9",
            branches: [
              {
                label: "Desplains",
                id: "10",
                branches: [],
              },
              {
                label: "Oak Lawn",
                id: "11",
                branches: [],
              },
            ],
          },
          {
            label: "Northwest Region",
            id: "12",
            branches: [
              {
                label: "East Morland",
                id: "13",
                branches: [],
              },
            ],
          },
        ],
      },
      {
        label: "New York",
        id: "14",
        branches: [
          {
            label: "Manhattan",
            id: "15",
            branches: [],
          },
          {
            label: "Queens",
            id: "16",
            branches: [],
          },
          {
            label: "5372 Arlington Heights",
            id: "17",
            branches: [],
          },
          {
            label: "The Earlmore Institute of Health",
            id: "18",
            branches: [],
          },
        ],
      },
    ],
  },
]

The end product:

Building a Reusable Component

First, we’ll import React and create some styled Material UI components.

import React, { Fragment, useState } from "react"
import { styled, makeStyles } from "@material-ui/core/styles"
import ExpandMoreIcon from "@material-ui/icons/ExpandMore"
import ChevronRightIcon from "@material-ui/icons/ChevronRight"
import Box from "@material-ui/core/Box"

// styles

const StyledLabel = styled(Box)({
  height: "24px",
  "&:hover": {
    cursor: "pointer",
  },
})
const StyledTreeItem = styled(Box)({
  display: "flex",
  flexDirection: "row",
  alignItems: "center",
})
const StyledTreeChildren = styled(Box)({
  paddingLeft: "10px",
})

Props

Here are the prop shapes that we’ll use to build our components:

interface TreeItemProps {
  readonly id: string
  readonly onSelectCallback: (e: React.MouseEvent<HTMLInputElement>) => void
  readonly label: string
  readonly isSelected: boolean | undefined
  readonly children: ReadonlyArray<JSX.Element>
}

interface RecursiveTreeProps {
  readonly listMeta: Tree
  readonly onSelectCallback: (value: TreeBranch) => void
}

TreeItem

This will be our most atomic component, reused anywhere an item is rendered by the data we pass to our tree. This component can contain more of itself in a nested fashion, allowing us to render them recursively.

This component needs:

1. onSelectCallback - to power what happens when we click the item.
2. label - to display names of organizations (in our case).
3. children - to display nested items if they exist.
4. isSelected - to specify pre-selected items in the fetched data (as opposed to clicking to select the item).

const TreeItem = ({
  onSelectCallback,
  label,
  isSelected,
  children,
}: TreeItemProps) => {
  const [isOpen, toggleItemOpen] = useState<boolean | null>(null)
  const [selected, setSelected] = useState(isSelected)

  return (
    <div>
      <StyledTreeItem>
        {children.length > 0 && (
          <Box
            className="icon-container"
            onClick={() => toggleItemOpen(!isOpen)}
          >
            {isOpen ? <ExpandMoreIcon /> : <ChevronRightIcon />}
          </Box>
        )}
        <StyledLabel
          className="label"
          onClick={(e: React.MouseEvent<HTMLInputElement>) => {
            setSelected(!selected)
            onSelectCallback(e)
          }}
          style={{
            marginLeft: `${children.length === 0 ? "24px" : ""}`,
            background: `${selected ? "#d5d5d5" : ""}`,
          }}
        >
          {label}
        </StyledLabel>
      </StyledTreeItem>
      <StyledTreeChildren>{isOpen && children}</StyledTreeChildren>
    </div>
  )
}

Recursive Tree

This will be the workhorse component where our recursive logic lives. We pass our data here through listMeta to recursively render our TreeItem component as follows:

This component needs:

1. listMeta - the shape of our tree data.
2. onSelectCallback - to be passed down to TreeItems.

const RecursiveTree = ({ listMeta, onSelectCallback }: RecursiveTreeProps) => {
  const createTree = (branch: TreeBranch) =>
    branch.branches && (
      <TreeItem
        id={branch.id}
        key={branch.id}
        onSelectCallback={(e: React.MouseEvent<HTMLElement>) => {
          onSelectCallback(branch)
        }}
        isSelected={branch.selected}
        label={branch.label}
      >
        {branch.branches.map((branch: TreeBranch) => {
          return <Fragment key={branch.id}>{createTree(branch)}</Fragment>
        })}
      </TreeItem>
    )

  return (
    <Box>
      {listMeta.map((branch: TreeBranch, i: any) => (
        <Box key={i}>{createTree(branch)}</Box>
      ))}
    </Box>
  )
}

Our Functional Tree in Use

Check out the Github repo here.

Some Final Thoughts

Recursion can be a crafty tool in a developer’s arsenal. But as we build a recursive pattern to have a lot of moving parts, complexity and drawbacks can start to manifest. There’s no magic associated with this concept. Most of the problems that can be solved by recursion are likely able to be solved with iterative loops. When recursive solutions seem tempting, make sure to consider the potential drawbacks.

When Not to Use Recursion

There are generally more reasons not to use recursion than to do so. Yes, it can be exciting to delve into an abstract solution, but a good engineer weighs the potential downsides, which we'll go over here.

• Results in code that's harder to read or comprehend

Recursion isn’t a pattern developers come across every day. When implemented, you’re bound to catch future developers off guard, which is a noteworthy downside. Difficulty comprehending the pattern at a later date is likely to occur, not only when teammates peak at the code, but also when you happen to return to your own code six months later.

This can be mitigated by extensively documenting and commenting your code. Explain to future developers (and yourself) why and where recursion occurs. For example, above the function, add a doc comment including an obvious note, such as, "This function is recursive. It calls itself in order to render all descendents." A comment directly above the line where recursion occurs can also be helpful to call out.

• Can make maintenance and debugging a nightmare

Developers maintaining the codebase in the years to come could potentially see this pattern in a bad light. When others (or even you) come back to the code, the recursive solution may not be self-explanatory. If new features need to be added or bugs show up, getting to the bottom of what’s happening may be harder with a pattern like this.

• Can lead to performance issues when processing large amounts of data

Recursion can be a memory-intensive operation with larger data sets. A function repeatedly calling itself will consume more memory when compared to an iterative loop. If your data set is not large, then pay no mind. But if a recursive solution is implemented in an environment where resources are scarce and the data is hefty enough, you could run out of memory. Recursion can also be slow unless implemented carefully. For example, if each call to the function recomputes some value, but the result is actually the same for every iteration, or the same for each level in the tree, the function will be doing unnecessary repeated computations that could be avoided by applying memoization techniques.

In the End

There can be good reasons to avoid recursion. But if your case doesn't have any of these red flags and you know your data set will always comfortably fit within your available memory, it can be a great solution to have up your sleeve.