Introduction

Traversing a tree or graph with tail recursion is possible, but only if you change the shape of the algorithm. The usual direct recursive traversal is often not tail-recursive, so the standard trick is to carry your own explicit work list and make the recursive call the last operation.

Why Ordinary Recursive Traversal Is Often Not Tail-Recursive

Consider a classic binary-tree traversal. The recursive call is usually followed by more work, which means it is not in tail position.

For example, an inorder traversal conceptually does this:

1. visit left subtree
2. process current node
3. visit right subtree

Because the function still has work to do after the left-recursive call returns, the call is not tail-recursive. That means a language cannot optimize it into a loop-like structure automatically.

Tail Recursion Needs an Explicit Stack

To make traversal tail-recursive, move the pending work into an accumulator or explicit stack. Then the recursive step can be the final operation.

A tree depth-first traversal in Scala can be written like this:

1import scala.annotation.tailrec
2
3sealed trait Tree
4case object Empty extends Tree
5case class Node(value: Int, left: Tree, right: Tree) extends Tree
6
7object TailRecursiveTreeTraversal {
8  @tailrec
9  def preorder(todo: List[Tree], visited: List[Int] = Nil): List[Int] = todo match {
10    case Nil => visited.reverse
11    case Empty :: rest => preorder(rest, visited)
12    case Node(value, left, right) :: rest =>
13      preorder(left :: right :: rest, value :: visited)
14  }
15
16  def main(args: Array[String]): Unit = {
17    val tree = Node(1, Node(2, Empty, Empty), Node(3, Empty, Empty))
18    println(preorder(List(tree)))
19  }
20}

The recursive call to preorder(...) is the last thing the function does. The pending nodes live in todo, not in the call stack.

The Same Idea Works for Graphs

Graphs need one extra piece of state: a visited set. Without it, cycles can produce infinite traversal.

1import scala.annotation.tailrec
2
3object TailRecursiveGraphTraversal {
4  @tailrec
5  def dfs(
6      todo: List[String],
7      graph: Map[String, List[String]],
8      seen: Set[String] = Set.empty,
9      order: List[String] = Nil
10  ): List[String] = todo match {
11    case Nil => order.reverse
12    case node :: rest if seen.contains(node) =>
13      dfs(rest, graph, seen, order)
14    case node :: rest =>
15      val neighbors = graph.getOrElse(node, Nil)
16      dfs(neighbors ::: rest, graph, seen + node, node :: order)
17  }
18
19  def main(args: Array[String]): Unit = {
20    val graph = Map(
21      "A" -> List("B", "C"),
22      "B" -> List("D"),
23      "C" -> List("D"),
24      "D" -> Nil
25    )
26
27    println(dfs(List("A"), graph))
28  }
29}

This is still depth-first search. The difference is that the traversal state is explicit.

Tail Recursion Is Not Magic

Tail recursion does not remove the need to store unfinished work. It only changes where that work is stored.

In a non-tail-recursive DFS, the call stack remembers where to return.

In a tail-recursive DFS, your todo list or queue remembers what still needs processing.

That is the important mental model. Tail recursion is really recursion plus an explicit continuation structure.

BFS and DFS Are Both Possible

The container you carry determines the traversal style:

• use a stack-like work list for depth-first traversal
• use a queue-like work list for breadth-first traversal

For example, the Scala graph example above behaves like DFS because new neighbors are prepended ahead of the remaining work. If you append differently or use a queue structure, you move toward BFS behavior.

Language Support Matters

Tail recursion only helps with stack usage if the language or compiler actually optimizes it.

Examples:

• Scala can verify tail recursion with @tailrec
• Scheme-family languages commonly optimize tail calls
• Python does not perform tail-call optimization
• Java and C# do not guarantee it for ordinary code

That means a tail-recursive algorithm written in Python is still tail-recursive in shape, but it does not gain the same stack-safety benefit you would expect in a language with reliable tail-call optimization.

When Iteration Is Simpler

Once you make the work list explicit, an ordinary loop often becomes just as readable as tail recursion. In languages without dependable tail-call optimization, iteration is usually the more pragmatic choice for production traversal code.

Tail recursion is most valuable when:

• the language optimizes it well
• you want a functional style
• you want recursion without unbounded call-stack growth

If none of those apply, an explicit iterative loop may be clearer.

Common Pitfalls

The biggest mistake is assuming any recursive traversal becomes tail-recursive just because the function calls itself. Tail recursion specifically means the recursive call is the final operation.

Another mistake is trying to tail-recursively traverse a graph without a visited set. Cycles will eventually break the algorithm.

Developers also forget that tail recursion depends on language support. Writing a tail-recursive function in Python does not magically remove recursion-depth limits.

Finally, if you convert a traversal to tail recursion by adding a work list, make sure the work list order still matches the traversal order you intended.

Summary

• Ordinary tree and graph traversals are often not tail-recursive in their direct recursive form.
• To make them tail-recursive, move pending work into an explicit stack or queue.
• Graph traversals also need a visited set to handle cycles safely.
• Tail recursion helps with stack usage only in languages that optimize tail calls.
• In languages without that optimization, an explicit iterative traversal is often the better production choice.