/* Functional Programming Example -- Fibonacci
   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 Fibonacci number module from an Elixir version, which
as, 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:
- Use double (tree) recursion in fib
- Use two accumulating parameters (accumulators) in fib2's auxiliary
- States complexity measures

*/

object Fibonacci {

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

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

    def fib2(n: Int): Int = {

        // Tail recursive auxiliary function using accumulating parameters p and q
        // called only when n > 0
        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")
    }

  // Should implement extensive tesing externally
  def main(args: Array[String]) {
    for(i <- 0 to 12) {
      print  ("fib(" + i + ") is "  + fib(i) + "\t\t")
      println("fib2(" + i + ") is " + fib2(i) )
    }
    //print("fib2(-1) is ")
    //println(fib2(-1))
  }

}