recursion

gistfile1.swift

import Foundation

var title = "fibonacci sequence"

func fib1(n: Int) -> Int {
    switch n {
    case 0: return 0
    case 1: return 1
    default: return fib1(n-1) + fib1(n-2)
    }
}

func fib2(n: Int) -> Int {
    func fibIter(a: Int, b: Int, count: Int) -> Int {
        if count == 0 {
            return b
        } else {
            return fibIter(a+b, b: a, count: count-1)
        }
    }
    return fibIter(1, b: 0, count: n)
}
func fib3(n: Int) -> Int {
    guard n > 1 else {
        return n
    }
    var count = n, x = 0, y = 1
    repeat {
        (x, y) = (y, x+y)
        count--
    } while count > 1
    return y
}
func fib4(n: Int) -> Int {
    var tmpArray = [0, 1]
    func fib4Inside(m: Int) -> Int {
        if m >= tmpArray.count {
            tmpArray.append(fib4Inside(m-1) + fib4Inside(m-2))
        }
        return tmpArray[m]
    }
    
    return fib4Inside(n)
}

func fib5(n: Int) -> Int {
    guard n > 1 else {
        return n
    }
    var count = n+1, x = 0 , y = 1
    if count % 2 != 0 {
        (x, y) = (y, x+y)
        count--
    }
    var countHalf = count/2
    repeat {
        (x, y) = (x+y, x+2*y)
        countHalf--
    } while countHalf > 1
    return y
}

let x = 20

fib1(x)
fib2(x)
fib3(x)
fib4(x)
fib5(x)

title = "coin change"

func cc1(amount: Int, denomination: Array<Int>) -> Int {
    if amount < 0 || denomination.count == 0 { return 0 }
    if amount == 0 { return 1 }
    var deno = denomination
    deno.removeLast()
    return cc1(amount - denomination[denomination.count-1], denomination: denomination) + cc1(amount, denomination: deno)
}

func cc2(amount: Int, denomination: Array<Int>) -> Int {
    var table = Array(count: amount+1, repeatedValue: Array(count: denomination.count+1, repeatedValue: -1))
    var i = 0, j = 0
    while j < denomination.count+1 {
        table[0][j] = 1
        j++
    }
    while i < amount+1 {
        table[i][0] = 0
        i++
    }
    func cc2Inside(amount2: Int, denomination2: Array<Int>) -> Int {
        if amount2 < 0 {
            return 0
        }
        if table[amount2][denomination2.count] == -1 {
            var deno = denomination2
            deno.removeLast()
            table[amount2][denomination2.count] = cc2Inside(amount2-denomination2[denomination2.count-1], denomination2: denomination2) + cc2Inside(amount2, denomination2: deno)
        }
        return table[amount2][denomination2.count]
    }
    return cc2Inside(amount, denomination2: denomination)
}

func cc3(amount: Int, denomination: Array<Int>) -> Int {
    var table = Array(count: amount+1, repeatedValue: 0)
    table[0] = 1
    for(var i=0; i<denomination.count; i++) {
        for(var j=denomination[i]; j<=amount; j++) {
            table[j] += table[j-denomination[i]]
        }
    }
    return table[amount]
}

let y = 50
let denomination = [1, 5, 10, 20, 50, 100]

cc1(y, denomination: denomination)
cc2(y, denomination: denomination)
cc3(y, denomination: denomination)


title = "gcd"

func gcd(x x: Int, y: Int) -> Int {
    if y == 0 {
        return x
    } else {
        return gcd(x: y, y: x%y)
    }
}

gcd(x: 66, y: 55)