--[[ Functional Programming Example -- Factorial
     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 factorial functions are adapted from section 1.2.1 of Abelson
and Sussman's Structure and Interpretation of Computer Programs (SICP)
textbook.

--]]

-- Function "factorial" computes the factorial for nonnegative number
-- "n" using backward linear recursion. That is, the single recursive
-- call needed for each level is embedded in a larger expression whose
-- computation must be completed upon return from the recursive call.
-- Time complexity:  O(n) recursive calls of factorial
-- Space complexity: O(n) active calls each taking a frame

local function factorial(n)
  if type(n) == "number" and n >= 0 and n == math.floor(n) then
    if n == 0 then
      return 1
    else  -- n > 0 
      return n * factorial(n-1)  -- backward recursion
    end
  else
    error("Invalid argument to factorial: " .. tostring(n),2)
  end
end

-- Function "factorial2" computes the factorial for nonnegative number
-- "n" using a tail recursive auxiliary function with an accumulating
-- parameter.  Tail recursion is forward linear recursion. Auxiliary
-- function "fact_iter" is nested inside "factorial2" and can only be
-- called from "factorial2".
-- Time complexity:   O(n) recursive calls of fact_iter
-- Space complexity: O(1) with tail call optimization

local function factorial2(n)

  local function fact_iter(n,r) -- r is accumulating parameter
    if n == 0 then
      return r
    else  -- n > 0
      return fact_iter(n-1,n*r) -- tail recursion
    end
  end

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


-- Testing of factorial

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

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

-- Testing of factorial2

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

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