let rec fib n = if n < 2 then n else fib (n - 1) + fib (n - 2);;
fib 5;;
fib 98;;
fib 8;;
fib 10;;
fib 20;;
fib 30;;
fib 34;;
fib 35;;
#load "unix.cma";;
Unix.gettimeofday;;
Unix.gettimeofday ();;
let time f a = let s = Unix.gettimeofday () in
  let ret = f a in
  (ret, Unix.gettimeofday () -. s);;
time fib 35;;
time fib 36;;
let rec fibpair n = if n < 1 then (0, 1) else 
  let (f1, f2) = fibpair (n - 1) in (f2, f1 + f2);;
let fib2 n = fst (fibpair n);;
fib2 35;;
time fib2 35;;
time fib2 40;;
let rec mk n = if n = 0 then [] else n :: (mk (n - 1));;
mk 5;;
mk 5000;;
mk 500000;;
let rec mk2 acc n = if n = 0 then acc else mk2 (n :: acc) ( n - 1);;
let mk2a n = mk2 [] n;;
mk2a 5000;;
mk2a 500000;;
mk2a 5000000;;
mk2a 5;;
mk 5;;
let rec mk n = if n = 0 then [] else n :: (mk (n - 1));;
let rec mk2 acc n = if n = 0 then acc else mk2 (n :: acc) ( n - 1);;
let rec mk2 acc n = if n = 0 then List.rev acc else mk2 (n :: acc) ( n - 1);;
let rec len = function [] -> 0 | _ :: t -> 1 + len t;;
len [5;6;4;5];;
len (mk2 1000000);;;
len (mk2a 1000000);;;
let rec len2 acc = function [] -> acc | _ :: t -> len2 (1 + acc) t;;
let len2a l = len2 0 l;;
len2a [3;4;5;6;7];;
len2a (mk2a 1000000);;;
let rec rev = function [] -> [] | h :: t -> rev t @ [h];;
rev [5;6;7];;
let rec rev2 acc = function [] -> acc | h :: t -> rev2 (h :: acc) t;;
rev2 [] [5;6;7];;
time rev (mk2a 50000);;
time rev (mk2a 500);;
time rev (mk2a 5000);;
snd (time rev (mk2a 5000));;
snd (time rev2 [] (mk2a 5000));;
snd (time (rev2 []) (mk2a 5000));;