/*  Recursion Styles, Correctness, and Efficiency
    Scala Programs

1234567890123456789012345678901234567890123456789012345678901234567890

2019-01-30: Reconstructed and modified from Notes on Recursion Styles,
            Correctness, and Efficiency

*/

object RecursionStyles {

    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")
    }

    def fib(n: Int): Int = n match {
        case 0           => 0
        case 1           => 1
        case m if m >= 2 => fib(m-1) + fib(m-2) // double rec.
        case _          =>
            sys.error(s"Fibonacci undefined for $n")
    }

    def factorial2(n: Int): Int = {

        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")
    }

    def fib2(n: Int): Int = {

        def fibIter(n: Int, p: Int, q: Int): Int = n match {
            case 0 => p
            case m => fibIter(m-1,q,p+q)
        }

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

    def expt1(b: Double, n: Int): Double = n match {
        case 0          => 1
        case m if m > 0 => b * expt1(b,m-1)
        case _          =>
            sys.error(s"Cannot raise to a negative power $n")
    }

    def expt2(b: Double, n: Int): Double = {

        def exptIter(n: Int, p: Double): Double = 
	    n match {
                case 0 => p
                case m => exptIter(m-1,b*p)
            }

        if (n >= 0)
            exptIter(n,1)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

    def expt3(b: Double, n: Int): Double = {

        def exptAux(n: Int): Double = n match {
            case 0                 => 1
            case m if (m % 2 == 0) => // i.e. even
                val exp = exptAux(m/2)
                exp * exp             // backward recursion
            case m                 => // i.e. odd
                b * exptAux(m-1)      // backward recursion
        }

        if (n >= 0)
            exptAux(n)
        else
            sys.error(s"Cannot raise to negative power $n")
    }

    // Should implement extensive tesing externally
    def main(args: Array[String]) {
        println(s"factorial(6)   = ${factorial(6)}")
        println(s"fib(10)        = ${fib(10)}")
        println(s"factorial2(6)  = ${factorial2(6)}")
        println(s"fib2(10)       = ${fib2(10)}")
        println(s"expt1(2.0,10)  = ${expt1(2.0,10)}")
        println(s"expt2(2.0,10)  = ${expt2(2.0,10)}")
        println(s"expt3(2.0,10)  = ${expt3(2.0,10)}")
    }

}