fibonacci.nelua

require 'math'

do -- Recursive solution.
  local function fibonacci(n: integer): integer
    if n <= 2 then
      return 1
    end
    return fibonacci(n - 1) + fibonacci(n - 2)
  end
  print(fibonacci(10))
end

do -- Tail recursive solution.
  local function fibonacci(n: integer, current: integer, next: integer): integer
    if n == 0 then
      return current
    end
    return fibonacci(n - 1, next, current + next)
  end
  print(fibonacci(10, 0, 1))
end

do -- Iterative solution.
  local function fibonacci(n: integer): integer
    local first, second = 0, 1
    for i=1,n do
      first, second = second, first
      second = second + first
    end
    return first
  end
  print(fibonacci(10))
end

do -- Analytic solution.
  local function fibonacci(n: integer): integer
    local p = (1.0 + math.sqrt(5.0)) / 2.0
    local q = 1.0 / p
    return (@integer)(math.floor((p^n + q^n) / math.sqrt(5.0)))
  end
  print(fibonacci(10))
end