Fibonacci numbers generator in Swift 3

Question

The following Q&A covers a few methods of generating Fibonacci numbers in Swift, but it's quite outdated (Swift 1.2?):

• Sum of Fibonacci term using Functional Swift

Question: How could we generate Fibonacci numbers neatly using modern Swift (Swift >= 3)? Preferably methods avoiding explicit recursion.

Answer 1

Details

XCode Version 10.0 beta 6, Swift 4.2

The control flow is required to get either the first or the first two iterations of the fibonacci seq starting with 0.

Time Complexity: O(n)
Space Complexity: O(n)

Code

func fib(_ n: Int) -> [Int] {

 var fibs: [Int] = [0, 1]
 switch n
 {
 case 1:  return [fibs[0]]
 case 2:  return [fibs[0],fibs[1]]
 default:

 (2...n-1).forEach
 { i in
     fibs.append(fibs[i - 1] + fibs[i - 2])
 }

 return fibs
 }
}

Usage

fib(8)

//print(fib(8))

Answer 2

This is bad to use recursion!! recursion is evil!

I would have rather done it this way:

func fibo(_ n:Int) -> Int {

    var a = 0
    var b = 1

    for _ in 0..<n {
        a += b
        b = a - b
    }

    return a
}

Which is much faster and cleaner!

Answer 3

An alternative for Swift 3.0 would be to use the helper function

public func sequence<T>(first: T, while condition: @escaping (T)-> Bool, next: @escaping (T) -> T) -> UnfoldSequence<T, T> {
    let nextState = { (state: inout T) -> T? in
        // Return `nil` if condition is no longer satisfied:
        guard condition(state) else { return nil }
        // Update current value _after_ returning from this call:
        defer { state = next(state) }
        // Return current value:
        return state
    }
    return sequence(state: first, next: nextState)
}

from Express for loops in swift with dynamic range:

for f in sequence(first: (0, 1), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 1 1 2 3 5 8 13 21 34

Note that in order to include zero in the resulting sequence, it suffices to replace the initial value (0, 1) by (1, 0):

for f in sequence(first: (1, 0), while: { $1 <= 50 }, next: { ($1, $0 + $1)}) {
    print(f.1)
}
// 0 1 1 2 3 5 8 13 21 34

That makes the "artificial" check

if pair.1 == 0 { pair.1 = 1; return 0 }

redundant. The underlying reason is that the Fibonacci numbers can be generalized to negative indices (https://en.wikipedia.org/wiki/Generalizations_of_Fibonacci_numbers):

 ... -8, 5, -3, 2, -1, 1, 0, 1, 1, 2, 3, 5, 8, ...

Answer 4

Details

Xcode 9.3.1, Swift 4.1

Solution

extension Array where Element: BinaryInteger {

    private mutating func fibonacci(index: Int) {
        if index >= count {
            return
        }
        self[index] = self[index-1] + self[index-2]
        return fibonacci(index: index+1)
    }

    init(fibonacci count: Int) {
        self = [Element]()
        if count < 0 {
            self = [Element]()
        }
        self = [Element](repeating: 1, count: count)
        fibonacci(index: 2)
    }

    static func calculate(fibonacciAt index: Int) -> Element? {

        if index < 0 {
            return nil
        }

        if index < 2 {
            return 1
        }

        func calc(a: Element, b: Element, index: Int) -> Element {
            if index == 1 {
                return b
            }
            return calc(a: b, b: a+b, index: index-1)
        }

        return calc(a: 1, b: 1, index: index)
    }
}

Usage

let fibonacciSequence = [Int](fibonacci: 15)
let index = 12
print(fibonacciSequence)
print(fibonacciSequence[index])
let value = [Int].calculate(fibonacciAt: index)
print("\(value!)")

Results

Answer 5

In Swift 3.1, here's an iterator that generates Fibonacci numbers forever, and an infinite sequence derived from it:

class FibIterator : IteratorProtocol {
    var (a, b) = (0, 1)

    func next() -> Int? {
        (a, b) = (b, a + b)
        return a
    }
}

let fibs = AnySequence{FibIterator()}

To print the first 10 Fibonacci numbers:

> print(Array(fibs.prefix(10)))
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

If you want to filter or map this infinite sequence you'll need to call .lazy first, since otherwise filter or map will behave strictly and will not terminate. Here are the first 5 even Fibonacci numbers:

> print( Array(fibs.lazy.filter{$0 % 2 == 0}.prefix(5)) )
[2, 8, 34, 144, 610]

Answer 6

Using the global sequence(state:next:) function

Swift 3.0

As one alternative we could make use of one the neat global sequence functions, a pair of functions that were implemented in Swift 3.0 (as described in evolution proposal SE-0094).

• sequence(first:next:)
• sequence(state:next:)

Using the latter of these, we may keep the previous and current state of the Fibonacci numbers sequence as the mutable state property in the next closure of sequence(state:next:).

func fibs(through: Int, includingZero useZero: Bool = false)
    -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}
    // explicit type annotation of inout parameter closure
    // needed due to (current) limitation in Swift's type
    // inference

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int)
    -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        guard pair.1 <= through else { return nil }
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        })
}

Or, condensing this using tuple hacks (however executing next one extra, unnecessary, time)

func fibs(through: Int, includingZero useZero: Bool = false) -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: useZero ? (1, 0) : (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional<Int>.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

func fibs1(through: Int) -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1), next: { 
        ($0.1 <= through ? $0.1 : Optional<Int>.none, $0 = ($0.1, $0.0 + $0.1)).0 })
}

Note that we explicitly terminate the sequences with a nil return when the ... <= through condition is no longer met.

Example usage:

// fib numbers up through 50, excluding 0
fibs(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... or
fibs1(through: 50).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34

// ... including 0
fibs(through: 50, includingZero: true).forEach { print($0) }
    // 0 1 1 2 3 5 8 13 21 34

// project Euler #2: sum of even fib numbers up to 4000000
print(fibs(through: 4_000_000)
    .reduce(0) { $1 % 2 == 0 ? $0 + $1 : $0 }) // 4 613 732

We could also remove the termination criteria from above to construct an infinite sequence of fibonacci numbers, to be used in combination e.g. with prefix:

func infFibs() -> UnfoldSequence<Int, (Int, Int)> {
    return sequence(state: (0, 1), next: {
        (pair: inout (Int, Int)) -> Int in (pair.1, pair = (pair.1, pair.0 + pair.1)).0 })
}

// prefix the first 6 fib numbers (excluding 0) from
// the infinite sequence of fib numbers
infFibs().prefix(10).forEach { print($0) }
    // 1 1 2 3 5 8 13 21 34 55

Swift 3.1

When Swift 3.1 arrives, the prefix(while:) method for sequences, as described in evolution proposal SE-0045, will have been implemented. Using this additional feature, we can modify the fibs methods above to avoid the explicit by-nil conditional sequence termination:

func fibs(through: Int, startingFromZero useZero: Bool = false)
    -> AnySequence<Int> {
    return sequence(state: useZero ? (1, 0) : (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

// alternatively, always start from one: drop useZero 
// conditional at 'state' initialization
func fibs1(through: Int) -> AnySequence<Int> {
    return sequence(state: (0, 1),
                    next: { (pair: inout (Int, Int)) -> Int? in
        defer { pair = (pair.1, pair.0 + pair.1) }
        return pair.1
        }).prefix(while: { $0 <= through })
}

Examples should work the same as for Swift 3.0 above.