Recursive enumerations in Swift - Mini Project: Build & Apply

Recursive Enumerations in Swift

📖 Scenario: Imagine you are building a simple calculator that can handle addition and multiplication of numbers. You want to represent these calculations using a special kind of data structure called a recursive enumeration. This will help you understand how to model complex data that can contain itself.

🎯 Goal: Build a recursive enumeration in Swift to represent simple math expressions with numbers, addition, and multiplication. Then, write code to calculate the result of these expressions.

📋 What You'll Learn

Create a recursive enumeration called Expression with cases for number, addition, and multiplication.

Add a constant called expr that represents the expression (5 + 3) * 2 using the Expression enum.

Write a function called evaluate that takes an Expression and returns the calculated Int result.

Print the result of evaluating expr.

💡 Why This Matters

🌍 Real World

Recursive enumerations help model data that can contain itself, like math expressions, file systems, or nested menus.

💼 Career

Understanding recursive enums is useful for Swift developers working on compilers, interpreters, or complex data modeling in apps.

1

Create the recursive enumeration

Create a recursive enumeration called Expression with three cases: number(Int), addition(Expression, Expression), and multiplication(Expression, Expression).

Swift

# Your code here

Hint

Use the indirect keyword before enum to allow recursive cases.

2

Create an expression instance

Create a constant called expr that represents the expression (5 + 3) * 2 using the Expression enum cases.

Swift

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

# Your code here

Hint

Use nested enum cases to build the expression (5 + 3) * 2.

3

Write the evaluation function

Write a function called evaluate that takes an Expression parameter and returns an Int. Use a switch statement to handle each case and recursively calculate the result.

Swift

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

let expr = Expression.multiplication(
    .addition(.number(5), .number(3)),
    .number(2)
)

// Write the evaluate function below
# Your code here

Hint

Use recursion by calling evaluate inside the addition and multiplication cases.

4

Print the evaluation result

Write a print statement to display the result of calling evaluate on expr.

Swift

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

let expr = Expression.multiplication(
    .addition(.number(5), .number(3)),
    .number(2)
)

func evaluate(_ expression: Expression) -> 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)
    }
}

// Print the result of evaluating expr
# Your code here

Hint

The expression (5 + 3) * 2 equals 16.

Practice

1. What does the indirect keyword do in a Swift recursive enumeration?

easy

A. It allows the enum to refer to itself recursively.

B. It makes the enum immutable.

C. It converts the enum into a class.

D. It prevents the enum from being used in switch statements.

Solution

1. Step 1: Understand the role of indirect

   The indirect keyword tells Swift that the enum cases can hold references to the enum itself, enabling recursion.

2. Step 2: Identify what recursion means in enums

   Recursion means an enum case can contain another instance of the same enum, which requires indirect to avoid infinite size.

3. Final Answer:

   It allows the enum to refer to itself recursively. -> Option A

4. Quick Check:

   indirect enables recursion = C [OK]

Hint: Remember: indirect means self-reference allowed [OK]

Common Mistakes:

• Thinking indirect makes enum immutable
• Confusing indirect with class conversion
• Believing indirect disables switch usage

2. Which of the following is the correct syntax to declare a recursive enum case in Swift?

easy

A. enum Tree { case leaf(Int); indirect case node(Tree, Tree) }

B. enum Tree { case leaf(Int); case node(Tree, Tree) }

C. enum Tree { indirect case leaf(Int); case node(Tree, Tree) }

D. indirect enum Tree { case leaf(Int); case node(Tree, Tree) }

Solution

1. Step 1: Recall how to declare recursive enums

   Swift allows marking the whole enum as indirect to enable recursion for all cases.

2. Step 2: Check each option's syntax

   The syntax indirect enum Tree { case leaf(Int); case node(Tree, Tree) } correctly enables recursion by marking the whole enum indirect. Other options either lack the keyword, apply it only to non-recursive cases (leaving recursive case without), or contain syntax errors such as missing the case keyword.

3. Final Answer:

   indirect enum Tree { case leaf(Int); case node(Tree, Tree) } -> Option D

4. Quick Check:

   Whole enum indirect = A [OK]

Hint: Use 'indirect enum' for all recursive cases [OK]

Common Mistakes:

• Omitting indirect keyword
• Placing indirect only on some cases incorrectly
• Using indirect outside enum declaration

3. Given the recursive enum below, what is the output of print(tree.countLeaves())?

indirect enum Tree {
    case leaf(Int)
    case node(Tree, Tree)

    func countLeaves() -> Int {
        switch self {
        case .leaf(_): return 1
        case let .node(left, right):
            return left.countLeaves() + right.countLeaves()
        }
    }
}

let tree = Tree.node(.leaf(1), Tree.node(.leaf(2), .leaf(3)))

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Understand the tree structure

   The tree is: node(leaf(1), node(leaf(2), leaf(3))). It has three leaves: 1, 2, and 3.

2. Step 2: Count leaves recursively

   The countLeaves function returns 1 for each leaf and sums counts for nodes. So total leaves = 1 + (1 + 1) = 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Leaves counted = 3 [OK]

Hint: Count leaf nodes recursively for total leaves [OK]

Common Mistakes:

• Counting nodes instead of leaves
• Misunderstanding recursive calls
• Forgetting to sum both sides

4. Identify the error in this recursive enum declaration:

enum List {
    case end
    case node(Int, List)
}

medium

A. Missing indirect keyword for recursion.

B. Enum cases cannot have associated values.

C. The enum must be a class to be recursive.

D. The case end should have an associated value.

Solution

1. Step 1: Check for recursion support

   The enum List has a case node(Int, List) which refers to itself, so it is recursive.

2. Step 2: Verify use of indirect

   Swift requires marking recursive enums or cases with indirect. This enum lacks it, causing a compile error.

3. Final Answer:

   Missing indirect keyword for recursion. -> Option A

4. Quick Check:

   Recursive enum needs indirect = B [OK]

Hint: Add indirect to recursive enums or cases [OK]

Common Mistakes:

• Ignoring indirect keyword requirement
• Thinking recursion needs classes
• Assuming all enum cases need associated values

5. How would you modify this recursive enum to safely calculate the depth of a tree, returning 0 for leaves and the maximum depth for nodes?

indirect enum Tree {
    case leaf(Int)
    case node(Tree, Tree)

    func depth() -> Int {
        // Your code here
    }
}

hard

A. Return 1 for leaf, and sum depths of left and right nodes.

B. Return 0 for leaf, and 1 + max depth of left and right nodes.

C. Return 0 for leaf, and sum depths of left and right nodes.

D. Return 1 for leaf, and 1 + min depth of left and right nodes.

Solution

1. Step 1: Define depth for leaf nodes

   Leaves have depth 0 because they have no children.

2. Step 2: Define depth for node cases

   Nodes have depth 1 plus the maximum depth of their two child trees.

3. Final Answer:

   Return 0 for leaf, and 1 + max depth of left and right nodes. -> Option B

4. Quick Check:

   Depth = 0 for leaf, max + 1 for node = A [OK]

Hint: Depth = 0 leaf, 1 + max child depth node [OK]

Common Mistakes:

• Using sum instead of max for node depth
• Returning 1 for leaf depth incorrectly
• Using min instead of max for node depth