Category

# Recursive Enumerations in Swift

01 / Aug / 2017 by Piyush George 0 comments

Why use Recursion?

• When we say recursion, we are referring to a technique where an object is referring to itself.
• They’re useful where you need to do the representation of hierarchical structure like trees, network/graphs, which otherwise would be complicated to be represented using loops.
• It is possible to achieve recursion technique with reference types(class) since reference stores their instances.
• Because value types are copied unlike reference types, we cannot use them to achieve recursion.
• Since Swift made value types like `struct, ``enum `a first class citizen, it introduces a possibility of handling recursion with value type using a recursive enum.

What is Recursive Enum?

• Recursive Enums works on the above-mentioned principle of recursion.
• Let’s consider an example of representing Family Tree using the recursive enum. The scenario is shown in the figure below:

• In recursive enumeration, one or more cases have the type of an associated value to be the enumeration itself.
```indirect enum FamilyTree {
case noKnownParents
case oneKnownParent(name: String, ancestors: FamilyTreeOne)
case twoKnownParents(fatherName: String, fatherAncestors: FamilyTreeOne,
motherName: String, motherAncestors: FamilyTreeOne)
}
```

Or another syntax

```enum FamilyTree {
case noKnownParents
indirect case oneKnownParent(name: String, ancestors: FamilyTreeTwo)
indirect case twoKnownParents(fatherName: String, fatherAncestors: FamilyTreeTwo,
motherName: String, motherAncestors: FamilyTreeTwo)
}
```

The indirect keyword

• Recursive enums require the keyword `indirect` either before enum keyword or before the specific case.

So what’s the deal with this keyword indirect? Let’s understand how it works:

• For every instance created for a type in Swift, the compiler requires the knowledge of how much memory will it occupy.
• For a Swift enum, an instance of an enum will only have one case assigned to itself (which may change as your code runs) at any given point of time.
• The compiler now checks which case of the enum will occupy the maximum memory.
• Hence, the instance of enum created will have the required memory plus any additional requirement by the compiler for tracking which case is currently assigned.

Consider the below example :

```enum Area {
case square(side:Double)
}
```
• Since the case `square` has one associated value, the amount of the memory required to create an instance will be one Double’s worth of memory with any additional memory for tracking by the compiler.
• Similarly, the instance of the case `rectangle` will have the total memory  16 bytes + any additional memory for tracking.
• Now in `FamilyTree`  enum, the memory required for creating an instance of the case `oneKnownParent` will be the memory to hold a  String and an instance of `FamilyTree.`
• The compiler cannot determine how big a `FamilyTree` is or we could say that `FamilyTree` would require an infinite amount of memory.
• For this reason, we use the keyword `indirect `which instructs the compiler to store the enum’s data behind a pointer.
• The compiler now puts the data somewhere else in memory and creates a pointer to the associated data rather than making the instance of `FamilyTree` big enough to hold the data.

Example: Now let’s implement our above Family Tree by creating an instance of enum `FamilyTree`

```let fredAncestors = FamilyTree.twoKnownParents(
fatherName: "Fred Sr.",
fatherAncestors: .oneKnownParent(name: "Beth", ancestors: .noKnownParents),
motherName: "Marsha",
motherAncestors: .noKnownParents)
```

• If you check the size of the instance `fredAncestors,` it’s 8 bytes on a 64-bit architecture – the size of one pointer.
```MemoryLayout.size(ofValue:fredAncestors)
```

ExampleAnother common example of recursive enum is doing the arithmetic operation as shown below:

```indirect enum ArithmeticExpressions {
case number(Int)
case multiplication(ArithmeticExpressions, ArithmeticExpressions)
}
func evaluate(_ expression: ArithmeticExpressions) -> Int
switch expression {
case let .number(value):
return value