Recursion with lists in Swift

Recursion feels like a magical concept because many things happen behind the scenes while working with it. The programming paradigm is very powerful when used correctly but has quite a steep learning curve until you get it right.

In this tutorial you will learn all you need to know about recursion in Swift using a real world use case: simple linked lists. There are three main parts to cover in order to do this:

1. Create simple linked lists.
2. Print simple linked lists.
3. Print simple linked lists in reversed order.

That’s quite a lot, so let’s get started!

Create list nodes

There are no linked lists without any kind of nodes, so let’s just go ahead and simply create them first before doing anything else over there:

class Node {
  let value: Int
  var next: Node?
  
  init(value: Int, next: Node? = nil) {
    self.value = value
    self.next = next
  }
}

The Node class has a value and a node that points out to the next node in the linked list. Time to define the list itself!

Create simple linked lists

You use the previously declared Node class to create the List class:

class List {
  private let head: Node
  
  init(head: Node) {
    self.head = head
    create()
  }
  
  private func create() {
    // 1
    var current = head
    let nodes = Int.random(in: 1...9)
    // 2
    for _ in 0..<nodes {
      let value = Int.random(in: 1...10)
      let next = Node(value: value)
      current.next = next
      current = next
    }
  }
}  

Here’s what’s happening in the above code:

1. Set the list’s head as the current node of the list and use random numbers to determine the number of nodes in the list.
2. Loop through the list’s nodes while creating them. Each iteration creates a new node which you set as the next node of the current one. You use random numbers for node values and update the current node to use the next one in order to go through all nodes. 

That’s all you need to work with lists! Now let’s see how to print the list’s nodes.

Print list nodes

Add the following method to the List class to get started:

func show() {
  // 1
  print(head.value, terminator: " ")
  var current = head
  // 2
  while true {
    // 3
    guard let next = current.next else {
      print()
      break
    }
    // 4
    print(next.value, terminator: " ")
    current = next
  }
} 

There’s quite a lot going on over here, so let’s break it into steps:

1. Print the list’s head’s value and set the list’s head as the current node.
2. Go through the list’s nodes using an endless loop since you don’t know the number of nodes in the list.
3. Check if you have reached the end of the list and exit the loop if this is the case.
4. Print the next node’s value and set the current node to be the next one. This makes sure you go through all nodes.

Time to see if everything works:

let value = Int.random(in: 1...10)
let head = Node(value: value)
let list = List(head: head)
print("List:", terminator: " ")
list.show()

You use random numbers for the list’s head’s value. That’s all you have to do to create and print simple linked list nodes. What about printing them in reversed order? Recursion to the rescue!

Print list nodes in reversed order

Add the following methods to the List class to kick things off:

private func showReversed(start: Node?) {
  guard let start else {return}
  showReversed(start: start.next)
  print(start.value, terminator: " ")
}
  
func showReversed() {
  showReversed(start: head)
  print()
}

As you can see, the showReversed() method uses its showReversed(start:) overloaded method to print the list’s nodes in reversed order. Recursion happens when the showReversed(start:) method calls itself.

All recursive showReversed(start:) method calls are stored on the stack which works in LIFO mode. LIFO stands for last in first out and is a fancy way of saying that you can only add and remove items at the top of the stack. You can think of the stack as a pile of books or dishes. If you attempt to either add or remove anything in the middle or at the bottom of the stack everything else collapses. So it makes sense to only be able to work with the top item of the stack in this case no matter what.

The showReversed(start: head) method call doesn’t print anything if the list’s head is nil since it’s an empty list in this case and runs the showReversed(head.next) method call otherwise. Each showReversed(start:) method call runs the showReversed(start:) method call for the list’s next node if the current node isn’t nil. The compiler pushes all recursive showReversed(start:) method calls to the stack in the order they happen using the LIFO rule. This is how the stack trace looks like for a list with three nodes:

showReversed(start: head.next.next)
showReversed(start: head.next)
showReversed(start: head)

Once you reach the end of the list and the current node is nil, the compiler automatically unwinds the stack under the hood. Each recursive showReversed(start:) method call gets popped from the stack using the LIFO principle. The compiler first pops the showReversed(start: head.next.next) method call from the stack which prints head.next.next.value. The compiler then pops the showReversed(start: head.next) method call from the stack which prints head.next.value. The compiler finally pops the showReversed(list.head) method call from the stack which prints head.value. The stack is now empty so you are done.

It’s very important you make sure the chain of recursive showReversed(start:) method calls stops at some point so the compiler unwinds the recursive stack safely. Otherwise you get a stack overflow error. You can think of this as an endless loop with no exit condition.

Time to see how it all works:

print("Reversed list:", terminator: " ")
list.showReversed()

That’s all it takes to print simple linked list nodes in reversed order. This is what happens step by step with a list that has three nodes:

1. The showReversed() method call runs the showReversed(start: head) method call.
2. The stack pushes the showReversed(start: head) method call which checks that the list’s head isn’t nil since the list isn’t empty and runs the showReversed(start: head.next) method call.
3. The stack pushes the showReversed(start: head.next) method call which checks that head.next isn’t nil and runs the showReversed(start: head.next.next) method call.
4. The stack pushes the showReversed(start: head.next.next) method call which checks that head.next.next isn’t nil and runs the showReversed(start: head.next.next.next) method call.
5. The showReversed(start: head.next.next.next) method call checks that head.next.next.next is nil since you have reached the end of the list and returns.
6. The stack pops the showReversed(start: head.next.next) method call which prints head.next.next.value and returns.
7. The stack pops the showReversed(start: head.next) method call which prints head.next.value and returns.
8. The stack pops the showReversed(start: head) method call which prints head.value and returns.
9. The showReversed() method call finally returns.

I really do hope recursion doesn’t seem so magical to you anymore. Please definitely let me know if you have any questions or issues about the whole thing in the comments below. Happy coding!

Note: You can download the tutorial’s playground over here.

‹ To write or not to write a functional programming in Swift book?

Posted in Swift