The Fibonacci SequenceType
Swift sequences with a mathematical motive
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.^{1} 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^{2}:
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 nth 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 persondays 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 summingdoohickey (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 tradeoff 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.

Sum the first n Fibonacci numbers in linear time and constant space.

Sum the first n Fibonacci numbers in linear time and constant space.

Sum the first n Fibonacci numbers in linear time and constant space.
Luckily, Swift has just the features we need!

The
reduce
function, combined with the+
operator. 
The
prefix
function and lazy evaluation. 
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 GeneratorType
s, there’s only one requirement, which is to produce Element
s.
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 builtin 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 lineartime, constantspace, 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_{n1}  2T_{n2}, or x_n = rx_{n1}(1x_{n1}).
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[n1] + T[n2] }
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
.^{3}
// 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[n1] 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[n1] + T[n2] }
Or the “Tribonacci Numbers”, a thirdorder 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[n1] + T[n2] + T[n3] }
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[n1] * (1  x[n1]) }
}
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 constanttime formula to calculate Fibonacci numbers.

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

Your mileage may vary. ↩︎

I’m glossing over the fact that the Fibonacci numbers quickly become too large for Swift’s native
Int
. Larger values are definitely attainable, but beyond the scope of this article. ↩︎ 
Since the sequence is computed ondemand, this has the side effect that getting a new generator will effectively “branch off”, and further
next()
calls won’t affect other generators. This is also due to the value semantics ofArray
— each time our sequence gets copied, so does itsstorage
array. ↩︎