Functional Swift: Tail Recursion Explained

UPDATE: Swift doesn’t guarantee tail call optimization, so don’t rely on it. Thank @jl_hfl and @jckarter for pointing this out!

As I’ve been learning functional programming to become better at Swift, one concept that consistently comes up (at least in Haskell, which is what I’ve been focusing on), is tail recursion. It sounds scary at first, but it makes a lot of sense for iterating over finite lists.

The Terminology

Let’s say you have an array of numbers:

let numbers = [1,2,3,4,5]

The first element of the list is called head:

let head = numbers.first // {Some 1}

The array with all elements except the first one is called tail:

let tail = Array(dropFirst(myNumbers)) // [2,3,4,5]

Pretty simple, right? So how do you use this?

The Easy Way

Let’s say you want to write a function that adds up all the numbers in an array. The easy way to do this would be like this:

func sum(numbers: [Int]) -> Int {
    var sum: Int = 0
    
    for number in numbers {
        sum += number
    }
    
    return sum
}

let myNumbers = [1,2,3,4,5]
sum(myNumbers) // 15

Using Tail Recursion

Instead of using a for-loop and keeping track of the mutable sum variable (you can imagine this can get more complicated once you go beyond the sum), we can instead split the array into a head and a tail, and add each array element one at a time recursively until there are no more elements in the array:

func sumRecursively(numbers: [Int]) -> Int {
    if let head = numbers.first {
        let tail = Array(dropFirst(numbers))
        return head + sumRecursively(tail)
    } else {
        return 0
    }
}

let myNumbers = [1,2,3,4,5]
sumRecursively(myNumbers) // 15

UPDATE: Looks like I’m a little confused by the tail recursive terminology here… Thanks @marcelofabri_ for pointing out more resources on tail recursion.

Here is how you would solve this problem using tail recursion in Swift (thanks @marcelofabri_ again for putting it in a gist!):

func sumRecursively(numbers: [Int], _ total: Int = 0) -> Int {
    if let head = numbers.first {
        let tail = Array(dropFirst(numbers))
        return sumRecursively(tail, head + total)
    } else {
        return total
    }
}

let myNumbers = [1,2,3,4,5]
sumRecursively(myNumbers) // 15

One thing I found with Swift is that many APIs make it very easy to access elements in a sequence one at time (looking at you String Ranges), making it a lot easier to work with them using tail recursion vs doing for-loops. So this is definitely a must-know pattern for Swift. Enjoy!

Enjoy the article? Join over 20,000+ Swift developers and enthusiasts who get my weekly updates.