Recursive enumerations in Swift - Step-by-Step Execution

Concept Flow - Recursive enumerations

Define enum with case

↓

Case has associated value

↓

Associated value is enum itself

↓

Create instance recursively

↓

Use switch to match cases

↓

Process recursively

↓

Base case reached

↓

Return result

Recursive enumerations define cases that can hold instances of the same enum, allowing recursive data structures like trees or lists.

Execution Sample

Swift

indirect enum Number {
    case value(Int)
    case add(Number, Number)
}

let five = Number.value(5)
let sum = Number.add(five, Number.value(3))

Defines a recursive enum Number with values and addition, then creates instances representing 5 and 5 + 3.

Execution Table

Step	Action	Evaluation	Result
1	Define enum Number with cases value(Int) and add(Number, Number)	N/A	Enum type Number created
2	Create instance five = Number.value(5)	Number.value(5)	five holds value 5
3	Create instance Number.value(3)	Number.value(3)	Temporary instance holds value 3
4	Create instance sum = Number.add(five, Number.value(3))	Number.add(Number.value(5), Number.value(3))	sum holds add case with two Number values
5	Switch on sum to process	sum is add case	Extract left and right Number values
6	Process left: five is value(5)	value case with 5	Return 5
7	Process right: value(3)	value case with 3	Return 3
8	Add results 5 + 3	5 + 3	8
9	Return final result 8	N/A	Computation complete

💡 All recursive cases processed, base cases reached, computation finished

Variable Tracker

Variable	Start	After Step 2	After Step 4	Final
five	nil	Number.value(5)	Number.value(5)	Number.value(5)
sum	nil	nil	Number.add(Number.value(5), Number.value(3))	Number.add(Number.value(5), Number.value(3))
temporary Number.value(3)	nil	nil	Number.value(3)	Number.value(3)

Key Moments - 3 Insights

Why can an enum case hold the enum type itself?

Because Swift allows recursive enums with the 'indirect' keyword or by marking the enum indirect, enabling cases to hold instances of the same enum type, as shown in the execution_table step 4.

How does the recursion stop when processing the enum?

The recursion stops at base cases like 'value(Int)' which do not contain further enum instances, as seen in steps 6 and 7 where the value cases return directly.

What happens if we try to process an enum case without handling all cases in switch?

The code will not compile because Swift requires exhaustive switch statements on enums, ensuring all cases including recursive ones are handled, as implied in step 5.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what does the 'sum' variable hold?

A An enum case 'add' holding two Number instances

B An integer value 8

C An enum case 'value' holding 3

D Nil

💡 Hint

Check the 'Result' column in step 4 of execution_table

At which step does the recursion reach the base case for the left value?

A Step 5

B Step 7

C Step 6

D Step 8

💡 Hint

Look at the 'Action' and 'Evaluation' columns in steps 6 and 7

If we add another case to Number enum without updating the switch, what happens?

A The code compiles and runs normally

B The code fails to compile due to non-exhaustive switch

C The recursion never stops

D The enum loses recursive ability

💡 Hint

Refer to key_moments about exhaustive switch handling

Concept Snapshot

Recursive enumerations allow enum cases to hold instances of the same enum type.
Use 'indirect' keyword to enable recursion.
Process with switch statements handling all cases.
Base cases stop recursion.
Useful for trees, expressions, and linked structures.

Full Transcript

Recursive enumerations in Swift let you define enum cases that can hold instances of the same enum, enabling recursive data structures. The example defines an enum Number with two cases: value holding an integer, and add holding two Number instances. We create instances representing 5 and 5 + 3. Processing uses a switch statement that matches the add case, recursively processes left and right values, and sums them. The recursion stops at value cases which hold integers directly. This approach allows building and processing recursive data like expression trees. Swift requires exhaustive switch statements to handle all enum cases, ensuring safe recursion.

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