(* File: ocaml-recursion.ml *)

let rec nthsq n =         (* rec for recursion *)
   match n                  (* pattern matching for cases *)
   with 0 -> 0                  (* base case *)
   | n -> (2 * n -1)           (* recursive case *)
           + nthsq (n -1);;   (* recursive call *)

nthsq 3;;

let rec length list = match list
  with [ ] -> 0   (* Nil case *)
  | x :: xs -> 1 + length xs;;  (* Cons case *)

length [5; 4; 3; 2];;

let rec double_up list =
    match list
    with [ ] -> [ ]
       | (x :: xs) -> (x :: x :: double_up xs);;

let rec poor_rev list =
  match list
  with [] -> []
     | (x::xs) -> poor_rev xs @ [x];;

let rec doubleList list = match list
   with [ ] -> [ ]
   | x::xs -> 2 * x :: doubleList xs;;

doubleList [2;3;4];;

let doubleList list =
    List.map (fun x -> 2 * x) list;;

doubleList [2;3;4];;

let rec multList list = match list
  with [ ] -> 1
  | x::xs -> x * multList xs;;

multList [2;4;6];;

let multList list =
    List.fold_right
    (fun x -> fun p -> x * p)
    list 1;;

multList [2;4;6];;

let rec poor_rev list = match list
  with [] -> []
     | (x::xs) -> poor_rev xs @ [x];;

let rec naiveFib n = match n
  with 0 -> 0
  | 1 -> 1
  | _ -> naiveFib (n-1) + naiveFib (n-2);;

let rec rev_aux list revlist =
  match list with [ ] -> revlist
  | x :: xs -> rev_aux xs (x::revlist);;

let rev list = rev_aux list [ ];;

let rev list =
    List.fold_left
    (fun revlist -> (fun elt -> elt :: revlist))
    [] list ;;