## fibonacci series

in lua

recursion

### Source Code

``````-- Fibonacci series implementation
-- See: http://en.wikipedia.org/wiki/Fibonacci_number
-- Implementation note:
--  With respect to Lua's array numbering, with starts at 1,
--  the following assumes that, given a function F which returns
--  the i-th term in a Fibonacci series,
--  F(0) is undefined
--  F(1) = 1
--  F(2) = 1
--  F(n) = F(n-1) + F(n-2), given any n > 2

-- Custom memoization function
local function memoize(f)
local _cache = {}
return function (v)
local _result = _cache[v]
if not _result then _cache[v] = f(v) end
return _cache[v]
end
end

-- Recursive evaluation of fibonacci series
-- n: the i-th Fibonacci number

local function fib(n)
if n > 0 and n <= 2 then return 1 end
return fib(n-1) + fib(n-2)
end

-- Iterator for Fibonacci series
-- usage:
--  for count, value in fib_iter(limit) do ... end
local function fib_iter(n)
assert(n > 0, 'Expected n >= 0!')
return coroutine.wrap(function()
local a, b, k = 0, 1, 0
while k < n do
a, b = b, a+b
k = k + 1
coroutine.yield(k, a)
end
end)
end

return {
fib = memoize(fib),
fib_iter = fib_iter
}
``````
``````-- Tests for fib.lua
local fib      = (require 'fib').fib
local fib_iter = (require 'fib').fib_iter

local total, pass = 0, 0

local function dec(str, len)
return #str < len
and str .. (('.'):rep(len-#str))
or str:sub(1,len)
end

local function run(message, f)
total = total + 1
local ok, err = pcall(f)
if ok then pass = pass + 1 end
local status = ok and 'PASSED' or 'FAILED'
print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

run('Fails on running with no arg or 0', function()
assert(not pcall(fib))
assert(not pcall(fib, 0))
assert(not pcall(fib_iter))
assert(not pcall(fib_iter, 0))
end)

run('Evaluates the i-th term in fibonacci series', function()
local fib_values = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144}
for i,v in ipairs(fib_values) do
assert(v == fib(i))
end

for i,v in fib_iter(#fib_values) do
assert(fib_values[i], i,v)
end

end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
:format(total, pass, total-pass, (pass*100/total)))
``````