Swiftでフィボナッチ数列


Playgroundsで遊んでみた。

func fib(n:Int64) -> Int64 {
    if n==0 {
        return 0
    }else if n==1{
        return 1
    }
    return fib(n:n-1) + fib(n:n-2)
}
print(fib(n:20))

func fib2(n:Int64) -> (Int64, Int64) {
    if n==0 {
        return (0, 1)
    }
    let (x, y) = fib2(n:n-1)
    return (y, x+y)
}
print(fib2(n:20).0)

func fib3(n:Int64) -> ((Int64, Int64), (Int64, Int64)) {
    if n == 1 {
        return ((0, 1),
                (1, 1))
    }else if n%2==0 {
        let ((a, b), (c, d)) = fib3(n:n/2) 
        return ((a*a+b*c, b*(a+d)),
                (c*(a+d), d*d+b*c))
    }else{
        let ((a, b), (c, d)) = fib3(n:n-1) 
        return ((b,a+b),
                (d,c+d))
    }
}
print(fib3(n:20).0.1)

実行回数がリアルタイムで見れるのが便利。