/* 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
2019-01-29: Updated to match revised Recursion Styles notes

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)
        case _          =>
            sys.error(s"Factorial undefined for $n")
    }

    /* 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(n: Int, r: Int): Int = n match {
            case 0          => r
            case m if m > 0 => factIter(m-1,m*r)
        }

        if (n >= 0)            factIter(n,1)
        else
            sys.error(s"Factorial undefined for $n")
    }

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

}