{- Module ProgRecFun contains the functions from the course module
   Programming with Recursive Functions.  See that course module notes
   for discussion and explanation of these examples.

   Author: H. Conrad Cunningham, Professor
           Computer and Information Science
           University of Mississippi
   Date:   9 June 2016 (based on previous work)
-}

module ProgRecFun 
    (fact1, fact2, fact3, fact4, fact5, fact6, fib, fib2, expt, expt2, expt3)
where

fact1 :: Int -> Int 
fact1 n = if n == 0 then 
              1 
          else
              n * fact1 (n-1)

fact2 :: Int -> Int 
fact2 n 
  | n == 0    = 1 
  | otherwise = n * fact2 (n-1)

fact3 :: Int -> Int 
fact3 0 = 1 
fact3 n = n * fact3 (n-1)

fact4 :: Int -> Int 
fact4 n 
  | n == 0 =  1 
  | n >= 1 =  n * fact4 (n-1)

fact5 :: Int -> Int  
fact5 n = product [1..n]

fact6 :: Int -> Int 
fact6 n = factIter n 1 

factIter :: Int -> Int -> Int 
factIter 0 r         = r 
factIter n r | n > 0 = factIter (n-1) (n*r) 
  
fib :: Int -> Int
fib 0          = 0
fib 1          = 1 
fib n | n >= 2 = fib (n-1) + fib (n-2)

fib2 :: Int -> Int
fib2 n = fibIter n 0 1
    where
        fibIter 0 p q         = p
        fibIter m p q | m > 0 = fibIter (m-1) q (p+q)


{-  Function "expt" computes b^n (b raised to power n) using backward
    linear recursion.

    Time complexity:  O(n) recursive calls
    Space complexity: O(n) active recursive calls
    Termination: Argument decreases by 1 toward 0 in recursive call
-}

expt :: Integer -> Integer -> Integer
expt b 0        = 1
expt b n 
    | n > 0     = b * expt b (n-1)  -- backward recursion
    | otherwise = error ("expt not defined for negative exponent" 
                         ++ show n)


{-  Function "expt2" computes b^n using tail recursion.  

    Time complexity:  O(n) recursive calls 
    Space complexity: O(1) with tail call optimization 
    Termination:      Argument m of expt_iter decreases by 1 
                      toward 0 inrecursive call
-}

expt2 :: Integer -> Integer -> Integer
expt2 b 0       = 1
expt2 b n
    | n > 0     = exptIter n 1
    | otherwise = error ("expt2 not defined for negative exponent" 
                         ++ show n)
        where 
            exptIter 0 p = p  
            exptIter m p = exptIter (m-1) (b*p) -- tail recursion
 

{-  Function "expt3" computes b^n using a logarithmic algorithm and
    backward recursion.  It takes advantage of squaring.
   
        b^n = (b^(n/2)) * (b^(n/2)) if n even
        b^n = b * b^(n-1)           if n odd

     Time complexity:  O(log n) recursive calls
     Space complexity: O(log n) active recursive calls needing stack
                       frames
     Termination:      Argument n decreases either by one-half or 
                       by 1 toward 0 on the recursive calls
-}

expt3 :: Integer -> Integer -> Integer
expt3 b 0             = 1
expt3 b n  
    | n > 0 && even n = let exp = expt3 b (n `div` 2) in 
                            exp * exp      -- backward recursion
    | n > 0           = b * expt3 b (n-1)  -- backward recursion
    | otherwise = error ("expt3 not defined for negative exponent" 
                         ++ show n)        


-- Exercise:  Can you implement a tail recursive version of expt3?