--[[ Functional Programming Example -- Fibonacci
     H. Conrad Cunningham, Professor
     Computer and Information Science
     University of Mississippi

Developed for CSci 658, Software Language Engineering, Fall 2013

1234567890123456789012345678901234567890123456789012345678901234567890

2013-09-08: Completed prototype

These Fibonacci number functions are adapted from section 1.2.2 of
Abelson and Sussman's Structure and Interpretation of Computer
Programs (SICP) textbook.

--]]

-- Function "fib" takes nonegative number "n" and computes the nth
-- (second order) Fibonacci number using backward tree recursion.
-- Time complexity: O(fib n), more explosive than exponential
-- Space complexity: O(n)

local function fib(n)
  if type(n) == "number" and n >= 0 and n == math.floor(n) then
    if n == 0 then
      return 0
    elseif n == 1 then
      return n
    else  -- n > 1 
      return fib(n-1) + fib(n-2) -- double (tree) recursion
    end
  else
    error("Invalid argument to fib: " .. tostring(n), 2)
  end
end

-- Function "fib2" takes nonnegative number "n" and computes the nth
-- (second order) Fibonacci number.  It uses "fib_iter" a tail
-- recursive auxiliary function with two accumulating parameters.
-- Time complexity:    O(n) recursive calls
-- Space complextity:  O(1) with tail call optimization

local function fib2(n)

  local function fib_iter(a,b,m) -- accumulating parameters a and b
    if m == 0 then
      return b
    else  -- m > 0
      return fib_iter(a+b,a,m-1) -- tail recursion
    end
  end

  if type(n) == "number" and n >= 0 and n == math.floor(n) then
    return fib_iter(1,0,n)
  else
    error("Invalid argument to fib2: " .. tostring(n), 2)
  end
end


-- Testing of fib

local testvals = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,
                  15,16,17,18,19,20,30,33,35}

print("\nBackward recursive Fibonacci")
for _, v in ipairs(testvals) do
  print("fib(" .. tostring(v) .. ") = " .. fib(v))
end

-- Testing of fib2

print("\nTail recursive Fibonacci")
for _, v in ipairs(testvals) do
  print("fib2(" .. tostring(v) .. ") = " .. fib2(v))
end

print("\nForced error: Call with nonintegral argument.")
local v = 2.5
print("fib2(" .. tostring(v) .. ") = " .. fib2(v))