Demonstration of the power of simple dynamic programming using the fibonacci sequance

fibo.lua

local NUM_TO_CALC = 10

print("Fib1 - uses 'brute-force recursive method':")
print("-------------------------------------------")

local called = {}
-- hashmap to store call statistics

local function fib(n, depth)
	depth = depth or 1
	-- if no depth is provided, then it is 1

	print(string.rep(" ",depth)..tostring(n))
	-- print depth number of spaces, then the number we are calculating

	called[n] = called[n] and called[n]+1 or 1
	-- update call stats, called[n] is incremented
	-- (or initialized to 1)

	
	return 
	n==1 and 1 or -- 1 if n==1
		n==2 and 1 or -- 1 if n==2
			fib(n-1, depth+1) + fib(n-2,depth+1)
			-- the sum of the prev. 2 else
			-- depth  is incremented here
end

local start = os.clock()

print("Fib("..tostring(NUM_TO_CALC)..")="..tostring(fib(NUM_TO_CALC)))

local dt = (os.clock() - start)*1000
print("Elapsed "..tostring(dt).." seconds")
print("Call stats: ")
for k,v in pairs(called) do
	print("Fib("..tostring(k)..") calculated "..tostring(v).." times")
end
print("\n")

---------------------------------------------



print("Fib2 - uses caching of the results:")
print("-----------------------------------\n")

local cache = {}

local function fib(n)
	if n==1 or n==2 then
		return 1
	end

	if cache[n] then
		return cache[n]
	end

	local a = cache[n-1] or fib(n-1)
	local b = cache[n-2] or fib(n-2)

	local ret = a+b
	cache[n] = ret
	return ret
end


local start = os.clock()

print("Fib("..tostring(NUM_TO_CALC)..")="..tostring(fib(NUM_TO_CALC)))

local dt = (os.clock()-start)*1000

print("Elapsed "..tostring(dt).." second")