// 1
let rec sumList xs =
    match xs with
    | []    -> 0
    | y::ys -> y + sumList ys // w y jest pierwszy element, w ys reszta listy

[1..1000000] |> sumList // stack overflow


// 2

let sumListTailRecursive xs =
    let rec sumListTailRecHelper accumulator xs =
        match xs with
        | []    -> accumulator
        | y::ys -> sumListTailRecHelper (accumulator+y) ys
    sumListTailRecHelper 0 xs

[1..10000000] |> sumListTailRecursive

// pomiar wydajności

let sumListIter xs =
    let mutable sum = 0
    for a in xs do
        sum <- sum + a
    sum

let l = [for a in 1..10000 -> a]

let stopWatch = System.Diagnostics.Stopwatch.StartNew()
for _ in 1..100000 do
     l |> sumList |> ignore

stopWatch.Stop();
printfn "Rekurencja: %f" stopWatch.Elapsed.TotalMilliseconds

let stopWatch2 = System.Diagnostics.Stopwatch.StartNew()
for _ in 1..100000 do
     l |> sumListTailRecursive |> ignore

stopWatch2.Stop();
printfn "Rekurencja ogonowa: %f" stopWatch2.Elapsed.TotalMilliseconds

let stopWatch3 = System.Diagnostics.Stopwatch.StartNew()
for _ in 1..100000 do
     l |> sumListIter |> ignore

stopWatch3.Stop();
printfn "Iteracyjnie: %f" stopWatch3.Elapsed.TotalMilliseconds

let stopWatch4 = System.Diagnostics.Stopwatch.StartNew()
for _ in 1..100000 do
     List.sum l |> ignore

stopWatch4.Stop();
printfn "List.sum: %f" stopWatch4.Elapsed.TotalMilliseconds