SafeRecurrenceRelation.swift

// Much safer! Notice that `iteration` stops increasing after the initial terms are produced.
// Thanks @oisdk for pointing this out.

public struct RecurrenceRelation<Element>: SequenceType, GeneratorType
{
    private let recurrence: (T: [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.
    public init(_ initialTerms: [Element], _ recurrence: (T: [Element], n: Int) -> Element)
    {
        self.recurrence = recurrence
        storage = initialTerms
    }

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

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