A recursive data type is a type that contains other values of the same type as a property for the type. Recursive data types are used when we want to define dynamic data structures, such as lists and trees. The size of these dynamic data structures can grow or shrink depending on our runtime requirements.
Linked lists are perfect examples of a dynamic data structure that we would implement using a recursive data type. A linked list is a group of nodes that are linked together, where, in its simplest form, each node maintains a link to the next node in the list. The following diagram shows how a very basic linked list works:
Each node in the list contains some value or data, and it also contains the link to the next node in the list. If one of the nodes within the list loses the reference to the next node, the remainder of the list will be lost because each node is only aware of the next node in the list. Some linked lists maintain a link to both the previous and next nodes to allow us to move both forward and backward through the list.
The following code shows how we could create a linked list using a reference type:
class LinkedListReferenceType {
var value: String
var next: LinkedListReferenceType?
init(value: String) {
self.value = value
}
} In the LinkedListReferenceType class, we have two properties. The first property is named value and it contains the data for this instance. The second property is named next, which points to the next item in the linked list. If the next property is nil, then this instance will be the last node in the list. If we tried to implement this linked list as a value type, the code could look like the following code:
struct LinkedListValueType {
var value: String
var next: LinkedListValueType?
}When we add this code to a playground, we receive the following error:
Recursive value type 'LinkedListValueType' is not allowed
This tells us that Swift does not allow recursive value types. However, we are able to implement them in as a reference type, which we saw earlier.
I have never read anything official from Apple concerning the reason recursive value types are not allowed. However if we think about it, recursive value types are a really bad idea because of how value types function. Let's examine this for a minute because it will really stress the difference between value and reference types. It will also help you understand why there are times we would need to use reference types.
Let's say that we were able to create the LinkedListValueType structure without any errors. Now let's create three nodes for our list, as shown in the following code:
var one = LinkedListValueType(value: "One",next: nil) var two = LinkedListValueType (value: "Two",next: nil) var three = LinkedListValueType (value: "Three",next: nil)
Now we will link these nodes together with the following code:
one.next = two two.next = three
Do you see the problem with this code? If not, think about how a value type is passed. In the first line, one.next = two, we are not actually setting the next property to the two instance itself; we are setting it to a copy of the two instance. This means that in the next line, two.next = three, we are setting the next property of the two instance itself to the three instance. However, this change is not reflected back in the copy that was made for the next property of the one instance. Sounds a little confusing? Let's clear it up a little by looking at a diagram that shows the state of our three LinkedListValueType instances if we were able to run this code:
As we can see from the diagram, the next property of the one instance is pointing to a copy of the two instances whose next property is still nil. The next property of the original two instance, however, is pointed to the three instance. This means that if we try to go through the list by starting at the one instance, we would not reach the three instance because the copy of the two instances would still have a next property that is nil.
The second thing that we can only do with reference (class) types is inheritance.