(* Recursion Example *)
let rec nthsq n =
  match n with
    | 0 -> 0
    | n -> (2 * n - 1) + nthsq(n - 1);;

nthsq 3;;

(* Lists *)
let rec length lst = match lst with
  | [] -> 0
  | x::xs -> 1 + length xs;;

length [2;3;4;6];;

(* Forward recursion *)
let rec badReverse lst = match lst with
  | [] -> []
  | x::xs -> (badReverse xs) @ [x];;

badReverse [1;2;3;4;5];;

(* Mapping recursion *)
let rec doubleList lst = match lst with
  | [] -> []
  | x::xs -> 2 * x :: doubleList xs;;

doubleList [4;6;8];;

(* Generic Maps *)
let rec map f l =
  match l with
    | [] -> []
    | x::xs -> (f x) :: (map f xs);;

let double n = 2 * n;;

map double [1;2;3;4;5];;

(* List.map *)
List.map double [1;2;3;4;5];;

let doubleList list = List.map double list;;

doubleList [1;2;3;4;5];;

(* Folding recursion *)
let rec multList lst = match lst with
  | [] -> 1
  | x::xs -> x * multList xs;;

multList [2;4;6];;

(* Generic Folds: Fold Left *)
let rec fold_left f i l =
  match l with
    | [] -> i
    | x::xs -> fold_left f (f i x) xs;;

fold_left ( * ) 1 [2;4;6] ;;

(* Generic Folds: Fold Right *)
let rec fold_right f l i =
  match l with
    | [] -> i
    | x::xs -> f x (fold_right f xs i);;

fold_right ( * ) [2;4;6] 1;;

(* List.folds *)
List.fold_left ( * ) 1 [2;4;6];;

List.fold_right ( * ) [2;4;6] 1;;

(* Quadratic Time *)
let rec badReverse lst = match lst with
  | [] -> []
  | x::xs -> (badReverse xs) @ [x];;

(* Exponential Time *)
let rec badFib n = match n with
  | 0 -> 0
  | 1 -> 1
  | _ -> badFib (n-1) + badFib (n-2);;

(* Accumulating Recursion *)
let rec goodRevAux lst acc = match lst with
  | [] -> acc
  | x::xs -> goodRevAux xs (x::acc);;

let goodReverse lst = goodRevAux lst [];;

(* Problem 1 Solution *)
let rec maxlist lst = match lst with
  | [x] -> x
  | x::xs -> max x (maxlist xs);;

maxlist [5;3;7;23;4;0;19];;

(* Problem 2 Solution *)
let rec maxlistaux lst a = match lst with
  | [] -> a
  | x::xs -> maxlistaux xs (max x a);;

let maxlist (x::xs) = maxlistaux xs x;;

maxlist [5;3;7;23;4;0;19];;