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 14,500+ Swift developers and enthusiasts who get my weekly updates.

  • Scott

    Or you could just use Swift’s reduce method 🙂

    • Yes, this was the simplest example I could think of for the purpose of this article. There are def better ways to sum in Swift 🙂

  • chrisbrandow

    Thanks for this post. I learned a few things! Perhaps, it would clarify the point about tail-call recursion to preface your first recursion example with a slightly more explicit description that it is not a tail-call recursive function?

    I am very much learning about this stuff, so if my comment is in error, please feel free to simply delete it.

  • Gary

    Wonderful article! I am a late comer in programming, I am currently learning iOS programming, how can you learn programming so fast? May you give some advice to me?

  • codingTheHole

    I wonder if using defer might guarantee that a tail call is made?

  • Aki

    Thank you for this good post.
    There is one improvement point in sumRecursively , I think.

    func sumArray(ints: [Int?])->Int{
    if let head = ints.first {
    let tail = Array(ints.dropFirst())
    return head as Int! + sumArray(tail)
    }else{
    return 0
    }
    }

    print(sumArray([1,2,3,4,5])) // 15

    [var total] is no need for this function.