🎓 A1Learner
🔍
0 of 36 lessons completed

Swift Recursive Enums

A recursive enum is an enum whose cases can hold values of the same enum type. The indirect mark lets those cases store the nested values.

An expression tree

The tree adds 2 to the product of 3 and 4. The evaluate method calls itself on the left and right parts of each branch.

indirect enum Expression {
    case number(Int)
    case add(Expression, Expression)
    case multiply(Expression, Expression)
    func evaluate() -> Int {
        switch self {
        case .number(let value):
            return value
        case .add(let left, let right):
            return left.evaluate() + right.evaluate()
        case .multiply(let left, let right):
            return left.evaluate() * right.evaluate()
        }
    }
}
let tree = Expression.add(.number(2), .multiply(.number(3), .number(4)))
print(tree.evaluate())

Building a tree in pieces

Each value here is a small tree stored in a constant. The product wraps the sum, so its result builds on the sum result.

indirect enum Expression {
    case number(Int)
    case add(Expression, Expression)
    case multiply(Expression, Expression)
    func evaluate() -> Int {
        switch self {
        case .number(let value):
            return value
        case .add(let left, let right):
            return left.evaluate() + right.evaluate()
        case .multiply(let left, let right):
            return left.evaluate() * right.evaluate()
        }
    }
}
let two = Expression.number(2)
let sum = Expression.add(two, .number(3))
let product = Expression.multiply(sum, .number(4))
print(sum.evaluate())
print(product.evaluate())

A folder tree

A folder holds an array of items, and an item can itself be a folder. The totalSize method adds the size of every file in the tree.

indirect enum FileItem {
    case file(size: Int)
    case folder(files: [FileItem])
    func totalSize() -> Int {
        switch self {
        case .file(let size):
            return size
        case .folder(let files):
            var total = 0
            for item in files {
                total += item.totalSize()
            }
            return total
        }
    }
}
let root = FileItem.folder(files: [
    .file(size: 10),
    .folder(files: [.file(size: 5), .file(size: 7)]),
    .file(size: 3)
])
print(root.totalSize())

Example

indirect enum IntList {
    case end
    case node(Int, IntList)
    func sum() -> Int {
        switch self {
        case .end:
            return 0
        case .node(let value, let rest):
            return value + rest.sum()
        }
    }
}
let list = IntList.node(4, .node(6, .node(10, .end)))
print(list.sum())

Key points

  • The indirect mark sits before the enum keyword in the definition.
  • One indirect mark on the enum covers every case that holds a nested value.
  • A leaf case carries plain data and holds no nested value.
  • A recursive method reads one layer and calls itself on the nested values.
  • Each recursive call works on a smaller part of the tree.
  • The nesting ends when a call reaches a leaf case.

In this example, each node case holds one number and the rest of the list. The sum method adds 4, 6, and 10 as the calls move down the list. The end case adds nothing and stops the chain.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

Why does a recursive enum carry the indirect mark?