Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 146 ยท Structures, Classes and Enums

Indirect Enums and Recursive Types

Learn Swift indirect enums - why recursive enums need indirect, how to build expression trees, linked lists and binary trees, evaluate them recursively, and how they are stored in memory.

Some data contains smaller pieces of itself. An arithmetic expression such as (2 + 3) * 4 is a multiplication whose left side is itself an addition. A folder holds files and other folders. A list is either empty or a value followed by a shorter list. Types like these are called recursive: the definition of the type mentions the type.

Enums are a natural fit for recursive data, because each case can describe one shape of the structure. There is one catch. Swift stores an enum value inline, with a size known at compile time, and a type that contains itself directly would have infinite size. The indirect keyword is how you tell Swift to store the inner values on the heap instead. This lesson shows what the error looks like, how indirect fixes it, and how to write the functions that walk these structures. You should be comfortable with enumerations and with recursion first.

The problem: a type that contains itself

Let's try to model a tiny arithmetic language. An expression is either a number, or the sum of two expressions, or the product of two expressions:

Swift A recursive enum without indirect (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The compiler rejects it with error: recursive enum 'Expr' is not marked 'indirect', with a note pointing at the add case where the cycle begins. The reasoning is about size. To place an Expr on the stack, Swift must know how many bytes it needs. The add case holds two Expr values, and each of those could be an add holding two more, so the size would never settle. Compare a struct that contained itself: it would be rejected for the same reason.

indirect fixes it

Mark the enum indirect, and Swift stores the payload of each recursive case in a heap-allocated box and keeps just a pointer inline. A pointer has a fixed size, so the type is finite again:

Swift An indirect enum and a recursive evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Read the code the way the data is shaped. The switch has one branch for each case. The branch for .number is the base case: it returns directly. The branches for .add and .multiply call evaluate on the two smaller expressions and combine the answers. Every recursive call receives a strictly smaller piece, so the process must end.

The expression (2 + 3) * 4 becomes this tree, where each node is an enum value:

TEXT
multiply
โ”œโ”€โ”€ add
โ”‚   โ”œโ”€โ”€ number(2)
โ”‚   โ””โ”€โ”€ number(3)
โ””โ”€โ”€ number(4)

This tree is called an abstract syntax tree, or AST. Compilers, calculators, template engines and JSON parsers all work this way, and recursive enums are Swift's most direct tool for it. The expression calculator project builds a complete one.

Marking only some cases

You do not have to box everything. Writing indirect before a single case boxes only that case:

Swift indirect on individual cases

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Here leaf stays inline and only node uses a heap box. Marking the whole enum indirect is simpler and almost always fine; marking single cases is a small saving for enums where most values are not recursive.

Adding more operations

The strength of this design shows when you want a second function over the same data. You write another switch, and the compiler checks you covered every case. Here is a function that prints an expression as text, adding parentheses only where needed, and one that measures the depth of the tree:

Swift Printing and measuring the tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

Two small techniques appear here. A case can list several patterns that bind the same names, as in .add(let l, let r), .multiply(let l, let r), when the branches do the same thing. And case .number: ignores the payload entirely when you do not need it. Add a new case such as .subtract later, and both functions fail to compile until you handle it. That is the exhaustiveness check from the enumerations lesson working for you across a whole codebase.

Adding an operation (a new function with a switch) is easy with enums. Adding a new kind of node means touching every switch. Class hierarchies have the opposite balance. Pick the one that matches how your program will change.

A linked list as an enum

The classic recursive type is the singly linked list: it is either empty, or one element followed by another list. As an enum, that sentence is almost the code:

Swift A linked list built from an enum

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The enum is also generic, with the placeholder Element. The most interesting line is the last one: longer was built by putting one element in front of list, and list is untouched. This is called a persistent data structure. Because the enum is a value type and its boxes are never modified, many lists can safely share the same tail. Prepending takes constant time and copies nothing.

The same recursion principle gives you a binary search tree, where each node holds a value and two subtrees:

Swift A binary search tree

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with readLine()), it gets the next line from this box.

The in-order walk visits the left subtree, then the value, then the right subtree, so the numbers come out sorted. The duplicate 30 was ignored. Each inserting call builds new nodes along one path and shares everything else with the old tree.

Memory, copying and limits

indirect does not make an enum a reference type. Semantically it is still a value: assigning it logically copies it, and you cannot change a node in place. Underneath, Swift keeps the boxes immutable and reference counted, so a "copy" only increments a counter, and the box is freed when the last owner goes away.

That has three practical consequences:

  • Allocation cost. Each recursive node is a separate heap allocation. For a few thousand nodes this is irrelevant. For millions of elements, an array is much faster than a linked-list enum, because arrays store elements contiguously.
  • Deep structures and the stack. Evaluating the tree uses recursion, so a list of a hundred thousand nodes can exhaust the call stack in a recursive count or toArray. When depth is unbounded, loop with a while instead, or use an explicit stack.
  • No in-place edits. To change something deep inside, you rebuild the path from the root, as inserting does. That is cheap for balanced trees and is what makes sharing safe.

Release builds with optimization can turn some simple recursion into loops, but Swift does not guarantee tail-call elimination. Do not depend on it to keep a deep recursion from overflowing the stack.

Alternatives

An indirect enum is not the only way to build a recursive type. A class with optional references (var next: Node?) gives you a mutable linked list with identity, at the price of reference semantics and ARC. A struct holding an array of children works well for trees where each node has many children, such as a folder tree: struct Folder { var name: String; var children: [Folder] } is allowed because the array stores its elements on the heap. Reach for indirect enum when the data is naturally a set of alternatives (number or sum or product), you want exhaustive switch handling, and you prefer immutable values.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the compiler reject enum Expr { case add(Expr, Expr) }?

    An inline enum must have a fixed size. A case holding two values of the same type would never settle, so Swift asks for indirect, which stores the payload in a heap box.
  2. 2. What does indirect change?

    The enum remains a value type, but recursive payloads live in reference-counted boxes so that the inline size is fixed.
  3. 3. In a recursive function over a tree enum, what is the base case?

    The base case returns without recursing, which is what lets the recursion end.
  4. 4. After let longer = list.prepending("start"), what happens to list?

    Enum values are immutable values here. prepending creates a new head node that points at the old list, so both lists coexist and share the tail.
  5. 5. Which is the best reason to prefer an array over a linked-list enum for a million numbers?

    Each recursive node is its own heap allocation, so for large sequences the array is both smaller and faster, and it avoids deep recursion.

Summary

  • A recursive enum has a case that contains the enum itself; Swift needs indirect to give it a finite size.
  • indirect enum E { ... } boxes all recursive payloads; indirect case boxes a single case.
  • Walk a recursive enum with a recursive function and a switch: base cases return, recursive cases call the function on the smaller parts.
  • Expression trees, linked lists and binary trees are all natural recursive enums, and adding a case makes the compiler point at every switch to update.
  • The enum is still a value type; operations return new values and share unchanged parts.
  • Each node is a heap allocation, and deep recursion can overflow the stack, so prefer arrays or loops for very large data.

Next: Subscripts