Say you just learned about Swift for the first time. You’re so excited that you spend the next whole day practicing Swift. (Who wouldn’t?) By the following day you’ve become an expert, so you start offering daily Swift lessons to share your wisdom.

What’s that? Of course, I’d gladly be your first student! I catch on quickly, and after a day of practice, I’m ready to start teaching Swift lessons myself. We both keep teaching, and our students pick it up — and start teaching their own students — just as fast as we did.

What an exciting world to live in! But it poses a bit of a logistical problem. If Swift learners keep pouring into the city, the infrastructure will start to falter.

The mayor calls in her very best scientists. “We need accurate models! How many people will be using Swift each day? WHEN WILL THE MADNESS END?”

Modeling the Swiftening

To get a feel for the problem, let’s draw a diagram of what happens in the first few days:

It’s not really practical to keep doing this by hand, since the tree keeps branching quickly — we’d run out of space to keep adding new Swifters. But looking closely, a simple pattern emerges. On any particular day, the total number of Swifters (we’ll call it \(S_\text{today}\)) is whatever it was yesterday (\(S_\text{yesterday}\)), plus a new student for every available teacher.

But what’s the number of available teachers? Remember, it takes a day of learning and a day of practice for someone to become an expert in Swift.¹ So everybody who’s been present since the day before yesterday can take on a new student: \({\color{red}S_\text{today}} = {\color{blue}S_\text{yesterday}} + {\color{green}S_\text{day before yesterday}}\).

Now we’re getting somewhere! That formula is so simple, we can calculate it by hand:

(You can confirm that these numbers match our diagram above.) Now, I’ll let you in on a secret: if this sequence looks familiar, that’s because these are the Fibonacci numbers.

Like it or not, they’re everywhere — whether it’s flowers growing Fibonacci numbers of petals, trees with Fibonacci branches, or someone complaining it’s all just confirmation bias. As we discovered, the sequence is based on a simple pattern, and it’s easy to compute²:

var i = 0
var j = 1
while true {
    (i, j) = (j, i + j)
    print(i) // prints 1, then 1, then 2, 3, 5, 8, 13, 21, 34, 55...
}

Nothing more to see here — we’ve done it!

Haha, gotcha. We’ve just begun. The beauty of computers is that they can quickly answer questions that would be tedious for us to do by hand. Let’s try a few.

How many Swifters are there after 42 days?

We almost answered this question already; we just need to stop at 42 instead of going on forever.

var i = 0
var j = 1
for _ in 0..<42 {
    (i, j) = (j, i + j)
}

i // returns 267914296

That wasn’t so bad. We can handle something a little more complicated:

What about the \(n\)th day?

In a way, this is the exact same question. We just need to generalize a little. We’ll pull out 42 from our last answer, and replace it with a variable called n:

func nthFibonacci(n: Int) -> Int
{
    var i = 0
    var j = 1
    for _ in 0..<n {
        (i, j) = (j, i + j)
    }
    return i
}

nthFibonacci(42) // returns 267914296
nthFibonacci(64) // returns 10610209857723

How much Swift was written in the first week?

For simplicity, assume everybody writes Swift at about the same rate. Then to find the number of person-days of Swift written, we just need to add up the Fibonacci numbers each day:

func fibonacciSumUpTo(n: Int) -> Int
{
    var sum = 0
    for i in 0..<n {
        sum += nthFibonacci(i) // the number of people writing Swift on day i
    }
    return sum
}

fibonacciSumUpTo(7) // returns 33

Better Living through Gradual Simplification

Hold the phone! Swift’s standard library already has a function called reduce which can add numbers together. What are we doing writing our own?

[1, 1, 2, 3, 5, 8, 13].reduce(0, combine: +) // returns 33

That works nicely, but we had to write out the Fibonacci numbers \(1, 1, 2, 3, 5, 8, 13\) by hand. Wouldn’t it be better to use the nthFibonacci() function we wrote already?

Well, since these are successive Fibonacci numbers, we can start with a simple range of numbers from 1 through 7:

[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci) // returns [1, 1, 2, 3, 5, 8, 13]

[1, 2, 3, 4, 5, 6, 7].map(nthFibonacci).reduce(0, combine: +) // returns 33

Or here’s a further simplification using Swift’s inclusive range operator (...):

(1...7).map(nthFibonacci).reduce(0, combine: +) // returns 33

This is equivalent to fibonacciSumUpTo.

Performance Considerations

Looks great, but remember that nthFibonacci(i) starts from 0 and works its way up to \(i\), so the amount of work required scales up linearly with \(i\).

And since our summing-doohickey (1...n).map(nthFibonacci).reduce(0, combine: +) runs the nthFibonacci function on every number from 1 to \(n\), the total work grows quadratically with \(n\).

If we didn’t have to start over at 1 for each successive Fibonacci number, we could add them together with much less work. Let’s combine the nthFibonacci and fibonacciSumUpTo functions we had previously, and build up the total while calculating the numbers themselves at the same time:

func fastFibonacciSumUpTo(n: Int) -> Int
{
    var sum = 0
    var i = 0
    var j = 1
    for _ in 0..<n {
        (i, j) = (j, i + j) // calculate the next number
        sum += i // update the sum
    }
    return sum
}

fastFibonacciSumUpTo(7) // returns 33

Now, we’ve achieved linear instead of quadratic time complexity for fastFibonacciSumUpTo.

But in order to do this, we had to make a more complicated, specialized function. We’ve made a trade-off between separation of concerns (calculating the Fibonacci numbers and adding them together as separate steps) and performance.

The plan is to use the Swift standard library to simplify and untangle our code. First, let’s summarize what we’d like to do.

1. Sum the first \(n\) Fibonacci numbers in linear time and constant space.

2. Sum the first \(n\) Fibonacci numbers in linear time and constant space.

3. Sum the first \(n\) Fibonacci numbers in linear time and constant space.

Luckily, Swift has just the features we need!

1. The reduce function, combined with the + operator.

2. The prefix function and lazy evaluation.

3. Custom sequences, via the SequenceType protocol.

The Custom Sequence

The foundation of Swift’s for–in loops is the SequenceType protocol. Anything that adopts SequenceType can be looped over.

To be a SequenceType there is only one requirement, and that’s providing a Generator:

protocol SequenceType {
    typealias Generator: GeneratorType
    func generate() -> Generator
}

And for GeneratorTypes, there’s only one requirement, which is to produce Elements.

protocol GeneratorType {
    typealias Element
    mutating func next() -> Element?
}

So a sequence is something which can provide generators of elements.

The quickest way to make a custom sequence in Swift is with AnySequence. It’s a built-in struct that responds to generate() by calling a closure you give it at initialization.

struct AnySequence<Element>: SequenceType {
    init<G: GeneratorType where G.Element == Element>(_ makeUnderlyingGenerator: () -> G)
}

And similarly, to make the generator, we can make use of AnyGenerator and the anyGenerator function:

func anyGenerator<Element>(body: () -> Element?) -> AnyGenerator<Element>

So writing a Fibonacci sequence is really quite simple:

let fibonacciNumbers = AnySequence { () -> AnyGenerator<Int> in
    // To make a generator, we first set up some state...
    var i = 0
    var j = 1
    return anyGenerator {
        // ...and the generator modifies its state for each call to next().
        // (Does this look familiar?)
        (i, j) = (j, i + j)
        return i
    }
}

That’s it.

Now, since fibonacciNumbers is a SequenceType, we can use it in a for loop:

for f in fibonacciNumbers {
    print(f) // prints 1, then 1, then 2, 3, 5, 8, 13, 21, 34, 55...
}

And, we get prefix for free:

for f in fibonacciNumbers.prefix(7) {
    print(f) // prints 1, 1, 2, 3, 5, 8, 13, then stops.
}

Finally, let’s chain it with reduce:

fibonacciNumbers.prefix(7).reduce(0, combine: +) // returns 33

Great! This is linear-time, constant-space, and importantly it clearly communicates what we’re trying to do, without the noise from ... and map.

Flexibility

The goal so far has been to give ourselves better tools to answer specific questions about the Fibonacci numbers, as they pertain to people learning Swift (at frankly alarming rates).

Delving deeper, it might be natural to ask: why are we dealing with Fibonacci numbers in the first place? The sequence just so happens to match the scenario of The Swiftening, because of the pattern we discovered:

This formula does appear in our code as (i, j) = (j, i + j). But it’s buried deep inside AnySequence and anyGenerator. If we’re trying to write code that is clear — code that describes the problem it’s trying to solve and doesn’t require dissecting — we’d better make this a little more obvious.

The Fibonacci sequence is commonly written as

This is exactly the same as our \(S_\text{today}\) version, just with numbers for indices instead of words. Importantly, it alludes to the more general notion of recurrence relations. That’s fancy math talk for a sequence whose next value depends on some of its previous values. Other examples might be \(T_{n} = 3T_{n-1} - 2T_{n-2}\), or \(x_n = rx_{n-1}(1-x_{n-1})\).

When defining a recurrence relation, it’s also crucial to provide initial terms. We can’t simply proceed to calculate the Fibonacci numbers with (i, j) = (j, i + j) if we don’t know what i and j started at. In this case, our initial terms were i = 0 and j = 1 — or, since we waited to perform the calculation once before returning our first value, the initial terms are 1 and 1.

The order of a recurrence relation is the number of previous terms needed at each step. And there must be exactly that many initial terms given (otherwise, we wouldn’t have enough information to calculate the very next term).

That’s enough for us to design an API! To create a recurrence relation, you’d just need to provide initial terms and an actual recurrence:

struct RecurrenceRelation<Element>
{
    /// - Parameter initialTerms: The first terms of the sequence.
    ///     The `count` of this array is the **order** of the recurrence.
    /// - Parameter recurrence: Produces the `n`th term from the previous terms.
    init(_ initialTerms: [Element], _ recurrence: (T: UnsafePointer<Element>, n: Int) -> Element)
}

(We’re using UnsafePointer<Element> instead of just [Element] so that we can make T[n] work without actually storing all previously calculated terms.)

Now, our initial task gets even easier. How many people are writing Swift? Just plug in the formula.

let peopleWritingSwift = RecurrenceRelation([1, 1]) { T, n in T[n-1] + T[n-2] }

peopleWritingSwift.prefix(7).reduce(0, combine: +) // returns 33

So, how about that implementation?

Let’s get down to it.

struct RecurrenceRelation<Element>: SequenceType, GeneratorType
{

First we need some storage for elements, and a reference to the closure we’re being given.

    private let recurrence: (T: UnsafePointer<Element>, n: Int) -> Element
    private var storage: [Element]
    
    /// - Parameter initialTerms: The first terms of the sequence.
    ///     The `count` of this array is the **order** of the recurrence.
    /// - Parameter recurrence: Produces the `n`th term from the previous terms.
    init(_ initialTerms: [Element], _ recurrence: (T: UnsafePointer<Element>, n: Int) -> Element)
    {
        self.recurrence = recurrence
        storage = initialTerms
    }

To keep things relatively simple, we’re going to adopt both SequenceType and GeneratorType at the same time. For generate(), we’ll just return self.³

    // SequenceType requirement
    func generate() -> RecurrenceRelation<Element> { return self }

Now, the meat of it — for each call to next(), we produce the next value by calling the recurrence, and then save it in storage.

    // GeneratorType requirement
    private var iteration = 0
    mutating func next() -> Element?
    {
        // Produce all the initial terms first.
        if iteration < storage.count { return storage[iteration++] }
        
        let newValue = storage.withUnsafeBufferPointer { buf in
            // Call the closure with a pointer offset from the actual memory location,
            // so that T[n-1] is the last element in the array.
            return recurrence(T: buf.baseAddress + storage.count - iteration, n: iteration)
        }
        
        // Store the next value, dropping the oldest one.
        storage.removeAtIndex(0)
        storage.append(newValue)
        iteration++
        return newValue
    }
}

Keep in mind: there are many other ways to define custom sequences. CollectionType, SequenceType, and GeneratorType are just protocols, so you can adopt them in a way that suits your needs. That said, you probably won’t need to do it very often in practice — Swift’s standard library has got you covered most of the time. But if you feel the need for a custom data structure, the rest of your code will thank you if you make it conform to CollectionType or SequenceType.

More Examples

Now that we’ve got a generalized recurrence relation, we can calculate lots of things without much effort. How about the Lucas Numbers? Just the same as Fibonacci, but with different initial terms:

// 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521...
let lucasNumbers = RecurrenceRelation([2, 1]) { T, n in T[n-1] + T[n-2] }

Or the “Tribonacci Numbers”, a third-order recurrence with some interesting properties:

// 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504...
let tribonacciNumbers = RecurrenceRelation([1, 1, 2]) { T, n in T[n-1] + T[n-2] + T[n-3] }

With a little more work, we can visualize the chaotic bifurcation of the logistic map:

func logisticMap(r: Double) -> RecurrenceRelation<Double>
{
    return RecurrenceRelation([0.5]) { x, n in r * x[n-1] * (1 - x[n-1]) }
}

for r in stride(from: 2.5, to: 4, by: 0.005) {
    var map = logisticMap(r)
    for _ in 1...50 { map.next() } // consume some values to let it settle

    Array(map.prefix(10))[Int(arc4random_uniform(10))] // choose one of the next 10 values
}

Isn’t math neat?

Further Recommendations

• TED talk, The magic of Fibonacci numbers, by Arthur Benjamin.

• Binet’s Formula, for a nearly constant-time formula to calculate Fibonacci numbers.

• Arrays, Linked Lists, and Performance at Airspeed Velocity, with other interesting approaches to sequences, including discussion of ManagedBuffer.