/* Functional Programming Example -- Factorial
   H. Conrad Cunningham, Professor
   Computer and Information Science
   University of Mississippi

   Developed for CSci 555, Functional Programming, Spring 2016

1234567890123456789012345678901234567890123456789012345678901234567890

2016-02-10: Developed from 2015 Elixir version

I adapted this factorial module from an Elixir version, which was, in
turn, adapted from a Lua version, which was, in turn, adapted from the
Scheme code in section 1.2.1 of Abelson and Sussman's Structure and
Interpretation of Computer Programs (SICP).

I have only tested this minimally.

Scala and functional programming highlights:
- Uses match statements for integers
- Uses nested function definitions
- Calls sys.error for error exits
- Uses accumulating parameters (accumulator)
- Uses tail recursion
- States complexity measures

*/

object Factorial {
  
  /* 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
 */

  def factorial(n: Int): Int = n match {
    case 0          => 1
    case m if m > 0 => m * factorial(m-1)
  }

  /* 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 "factIter" 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
  */

  def factorial2(n: Int): Int = {

    // Tail recursive auxiliary function
    def factIter(n1: Int, r: Int): Int = n1 match {
      case 0          => r
      case m if m > 0 => factIter(m-1,m*r)
    }

    factIter(n,1)
  }

  // Should implement extensive tesing externally
  def main(args: Array[String]) {
    println("factorial(7) is  " + factorial(7) )
    println("factorial2(7) is " + factorial2(7))
  }

}