Fibonacci

Find value of nth fibonacci

Loop

var N = 10
var a = 0, b = 1, c = 1

for i = 3, N {
    a = b
    b = c
    c = a + b
}

puts c    // 55

Recursion

func fib(n) {
    if n < 2 {
        return n
    }
    
    return fib(n - 2) + fib(n - 1)
}

puts fib(10)    // 55

Big n may lead to stack overflow!

Cached

Just use a map to store calculated numbers.

var cache = {}

func fib(n) {
    if n < 2 {
        return n
    }
    
    // caching
    if !cache[n] {
        cache[n] = fib(n - 2) + fib(n - 1)
    }
    
    return cache[n]
}

puts fib(40)    // 102334155