Recursive Enumerations in Swift

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.

[code language=”objc”]
indirect enum FamilyTree {
case noKnownParents
case oneKnownParent(name: String, ancestors: FamilyTreeOne)
case twoKnownParents(fatherName: String, fatherAncestors: FamilyTreeOne,
motherName: String, motherAncestors: FamilyTreeOne)
}
[/code]

Or another syntax

[code language=”objc”]
enum FamilyTree {
case noKnownParents
indirect case oneKnownParent(name: String, ancestors: FamilyTreeTwo)
indirect case twoKnownParents(fatherName: String, fatherAncestors: FamilyTreeTwo,
motherName: String, motherAncestors: FamilyTreeTwo)
}
[/code]

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 :

[code language=”objc”]
enum Area {
case square(side:Double)
case rectangle(length: Double, breadth: Double)
}
[/code]

• 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

[code language=”objc”]
let fredAncestors = FamilyTree.twoKnownParents(
fatherName: "Fred Sr.",
fatherAncestors: .oneKnownParent(name: "Beth", ancestors: .noKnownParents),
motherName: "Marsha",
motherAncestors: .noKnownParents)
[/code]

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

[code language=”objc”]
MemoryLayout.size(ofValue:fredAncestors)
[/code]

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

[code language=”objc”]
indirect enum ArithmeticExpressions {
case number(Int)
case addition(ArithmeticExpressions, ArithmeticExpressions)
case multiplication(ArithmeticExpressions, ArithmeticExpressions)
}
func evaluate(_ expression: ArithmeticExpressions) -> Int
switch expression {
case let .number(value):
return value
case let .addition(left, right):
return evaluate(left) + evaluate(right)
case let .multiplication(left, right):
return evaluate(left) * evaluate(right)
}
}
let multiplicationEnumType = ArithmeticExpressions.multiplication(.number(4), .number(4))
evaluate(multiplicationEnumType)
[/code]