/* 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 (tree) recursion
  }

  /* 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 a and b
    // called only when n1 > 0
    def fibIter(a: Int, b: Int, n1: Int): Int = n1 match {
      case 0 => b
      case m => fibIter(a+b,a,m-1)
    }

    if (n >= 0)
      fibIter(1,0,n)
    else
      sys.error("Fibonacci undefined for negative value " + 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))
  }

}