find the nth lucas number in swift

To find the nth Lucas number, we can use a recursive formula or we can use dynamic programming to avoid recomputing values. Here is an implementation of both approaches in Swift:

main.swift
// Recursive approach
func nthLucasNumberRecursive(_ n: Int) -> Int {
    if n == 0 {
        return 2
    } else if n == 1 {
        return 1
    } else {
        return nthLucasNumberRecursive(n - 1) + nthLucasNumberRecursive(n - 2)
    }
}

// Dynamic programming approach
func nthLucasNumberDynamic(_ n: Int) -> Int {
    var a = 2
    var b = 1
    
    if n == 0 {
        return a
    }
    
    for _ in 2...n {
        let c = a + b
        a = b
        b = c
    }
    
    return b
}
496 chars
29 lines

The recursive approach uses a base case of n = 0 or n = 1, and computes the nth Lucas number by summing the (n-1)th and (n-2)th Lucas numbers. This approach has exponential time complexity.

The dynamic programming approach starts with the first two Lucas numbers and iteratively computes the next Lucas number by adding the previous two. This approach has linear time complexity.