Recursive enumerations in Swift

Introduction

Recursive enumerations let you create values that can contain other values of the same type. This helps model things like trees or nested lists easily.

When you want to represent a tree structure, like a family tree or file system.

When you need to model nested data, such as arithmetic expressions with operations inside operations.

When you want to create linked lists or other self-referential data structures.

When you want to process data that can contain smaller parts of the same kind.

Syntax

Swift

indirect enum EnumName {
    case simpleCase
    case recursiveCase(EnumName)
}

The indirect keyword tells Swift that the enum can hold values of its own type.

You can mark the whole enum as indirect or just specific cases.

Examples

This enum models arithmetic expressions that can be numbers or operations combining other expressions.

Swift

indirect enum ArithmeticExpression {
    case number(Int)
    case addition(ArithmeticExpression, ArithmeticExpression)
    case multiplication(ArithmeticExpression, ArithmeticExpression)
}

Here, only the node case is recursive, holding a value and the rest of the list.

Swift

enum LinkedList {
    case empty
    indirect case node(Int, LinkedList)
}

This enum models a simple chain that ends or points to another chain.

Swift

indirect enum SimpleRecursive {
    case end
    case next(SimpleRecursive)
}

Sample Program

This program defines a recursive enum to represent arithmetic expressions. It builds the expression (5 + 4) * 2 and evaluates it recursively.

Swift

import Foundation

indirect enum ArithmeticExpression {
    case number(Int)
    case addition(ArithmeticExpression, ArithmeticExpression)
    case multiplication(ArithmeticExpression, ArithmeticExpression)
}

func evaluate(_ expression: ArithmeticExpression) -> Int {
    switch expression {
    case .number(let value):
        return value
    case .addition(let left, let right):
        return evaluate(left) + evaluate(right)
    case .multiplication(let left, let right):
        return evaluate(left) * evaluate(right)
    }
}

// Build expression: (5 + 4) * 2
let five = ArithmeticExpression.number(5)
let four = ArithmeticExpression.number(4)
let sum = ArithmeticExpression.addition(five, four)
let two = ArithmeticExpression.number(2)
let product = ArithmeticExpression.multiplication(sum, two)

print("Expression evaluates to: \(evaluate(product))")

Important Notes

Time complexity depends on the size of the recursive structure; evaluation visits each node once, so O(n).

Space complexity is O(n) due to the call stack during recursion.

Common mistake: forgetting to mark enum or cases as indirect causes compiler errors.

Use recursive enums when data naturally nests or links to itself; for flat data, simpler types are better.

Summary

Recursive enums let you create self-referential data types.

Use indirect to tell Swift about recursion.

Great for trees, linked lists, and nested expressions.