# Week 7: tail recursionΒΆ

We first recapped what tail recursion is.

Then we recapped how to do `sum`

tail-recursively, namely by writing a function `sum'`

that accumulates the “sum so far”: `sum' xs n = n + sum xs`

.

Then we recapped how to do `rev`

tail-recursively, namely by writing a function `revap`

that accumulates the “rev so far”: `revap xs ys = rev xs @ ys`

.

Then we did `duplicates`

.

Dan wrote this on Facebook:

A follow-on to Bram’s tutorial where he started to discuss the dup function (which duplicates all elements in a list as in

`dup [1;2;3] = [1;1;2;2;3;3]`

) and its tail-recursive implementation. Note that in a tail-recursive implementation the ‘accumulator’ where you store the result will grow to the left and the ‘obvious’ implementation of dup will end up with the list in reverse order:let rec dup' xxs = function | [] -> xxs | x :: xs -> dup' (x :: x :: xxs) xs # dup' [] [1;2;3] ;; - : int list = [3; 3; 2; 2; 1; 1]The obvious solution is to simply reverse the list produced by dup’:

let dup xs = xs |> dup' [] |> List.rev # dup [1;2;3;4] ;; - : int list = [1; 1; 2; 2; 3; 3; 4; 4]This may seem like wasteful and inefficient but remember that reversing a list, also a tail-recursive operation, is in fact very fast and dup will be quite efficient. Not as efficient as the non-tail-recursive implementation:

let rec dupn = function | [] -> [] | x :: xs -> x :: x :: dupn xsBut in the same ballpark, with the advantage of tail recursion!

(* benchmarking *) let rec mkrlist xs = function | 0 -> xs | n -> mkrlist (Random.bits () :: xs) (n-1) let bm f n = let l = mkrlist [] n in let t0 = Sys.time () in let _ = f l in let t1 = Sys.time () in print_float (t1 -. t0); print_newline () # bm dupn 100000;; 0.028933 - : unit = () # bm dup 100000;; 0.037415 - : unit = () # bm dupn 1000000;; Stack overflow during evaluation (looping recursion?). # bm dup 1000000;; 0.299246 - : unit = ()

Bram added:

Great explanation, thanks!

To do it equation-style,

`dup'`

is doingdup' xxs ys = rev (dup ys) @ xxsand an example equation we have is

dup' [1; 2; 3] [4; 5; 6] = rev (dup [4; 5; 6]) @ [1; 2; 3] = rev (4 :: 4 :: dup [5; 6]) @ [1; 2; 3] = rev ([4; 4] @ dup [5; 6]) @ [1; 2; 3] = rev (dup [5; 6]) @ [4; 4] @ [1; 2; 3] = rev (dup [5; 6]) @ [4; 4; 1; 2; 3] = rev (dup [5; 6]) @ (4 :: 4 :: [1; 2; 3]) = dup' (4 :: 4 :: [1; 2; 3]) [5; 6]so we know

dup' xxs (y::ys) = dup' (y :: y :: xxs) ysand this is how Dan made the tail-recursive implementation of

`dup'`

. To find`dup xs`

for any`xs`

, just compute`rev (dup xs) @ []`

which is just`rev (dup xs)`

, and re-reverse the result.As with sum and rev in the tutorial, we first make a more complicated version (

`sum'`

,`revap`

,`dup'`

) so we can make an efficient version of the simple thing (`sum`

,`rev`

,`dup`

).Note: the arguments are in a different order than in the actual tutorial, I think.