Skip to content

Instantly share code, notes, and snippets.

@brascene
Last active March 12, 2023 09:10
Show Gist options
  • Save brascene/c5e2322e4905dfdcfa52f12c9f2e1bcd to your computer and use it in GitHub Desktop.
Save brascene/c5e2322e4905dfdcfa52f12c9f2e1bcd to your computer and use it in GitHub Desktop.
Get n-th fibonacci number in Swift
import Foundation
import CoreFoundation
// MARK: Without recursion
func fib(_ n: Int) -> Int {
guard n > 1 else { return n }
var arr = Array.init(repeating: 1, count: n)
for i in 2..<n {
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr.last!
}
// MARK: With recursion (a lot faster)
func fibR(_ n: Int) -> Int {
guard n > 1 else { return n }
return fibR(n - 1) + fibR(n - 2)
}
// MARK: Helper function for measure execution time
public func measure(label: String? = nil, tests: Int = 1, printResults output: Bool = true, setup: @escaping () -> Void = { return }, _ block: @escaping () -> Void) -> Double {
guard tests > 0 else { fatalError("Number of tests must be greater than 0") }
var avgExecutionTime : CFAbsoluteTime = 0
for _ in 1...tests {
setup()
let start = CFAbsoluteTimeGetCurrent()
block()
let end = CFAbsoluteTimeGetCurrent()
avgExecutionTime += end - start
}
avgExecutionTime /= CFAbsoluteTime(tests)
if output {
let avgTimeStr = "\(avgExecutionTime)".replacingOccurrences(of: "e|E", with: " × 10^", options: .regularExpression, range: nil)
if let label = label {
print(label, "▿")
print("\tExecution time: \(avgTimeStr)s")
print("\tNumber of tests: \(tests)\n")
} else {
print("Execution time: \(avgTimeStr)s")
print("Number of tests: \(tests)\n")
}
}
return avgExecutionTime
}
// MARK: Results
let timeNoR = measure(label: "Without recursion", printResults: true) {
let n = fib(10)
print("Without recursion: \(n)")
}
let timeR = measure(label: "Using recursion", printResults: true) {
let n = fibR(10)
print("Using recursion: \(n)")
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment