{"id":492,"date":"2011-04-05T21:37:47","date_gmt":"2011-04-05T20:37:47","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=492"},"modified":"2011-04-19T08:48:21","modified_gmt":"2011-04-19T07:48:21","slug":"introduciton-to-erlang-recursion-22","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/04\/05\/introduciton-to-erlang-recursion-22\/","title":{"rendered":"Introduciton to Erlang : Recursion (2\/2)"},"content":{"rendered":"
This entry is part 10 of 16 in the series Introduction to Erlang<\/a><\/div>

Accumulators<\/h3>\n

In several cases, as with the mlists:length\/1<\/code> example, the non-tail recursive function can be easily turned to a tail recursive one by using the notion of accumulator<\/i>. An accumulator is an extra argument introduced to a function in order to aggregate the partial results of the function. It turns the “bottom-up” collection of the final result to “top-down”.<\/p>\n

In order to add and initialize the accumulator argument one has to introduce an extra function definition.<\/p>\n

\r\ntlr(...) ->\r\n    tlr(..., Accumulator_initial_value).\r\n\r\n% the clause that \"breaks\" the recursion and\r\n% returns the result\r\ntlr(..., Accumulator) -> \r\n    Accumulator;\r\ntlr(..., Accumulator) ->\r\n    ...,\r\n    Accumulator_new_value = ...,\r\n    ...,\r\n    trl(..., Accumulator_new_value).\r\n<\/pre>\n
Notice that typically you would only export the tlr\/1<\/code> function and the tlr\/2<\/code> would remain for inner-module use and not visible to the module’s users.
\n<\/p>\n
Examples<\/h4>\n
mlists:reverse\/1<\/h5>\n
\r\n% a benchmark function in order to write\r\n% one argument less :-)\r\nbm(Fun, Args) ->\r\n    % the ?MODULE can be used instead of the\r\n    % name of the module\r\n    timer:tc(?MODULE, Fun, Args).\r\n\r\n% non tail recursive\r\nreverse([]) ->\r\n    [];\r\nreverse([H | T]) ->\r\n    reverse(T) ++ [H].\r\n\r\n% tail recursive\r\n% create an extra help function that will include\r\n% the accumulator as an extra argument\r\nreverse_tr(List) ->\r\n    % initialize the accumulator to the proper value\r\n    reverse_tr(List, []).\r\n\r\n% the help function\r\n% when finished, return the Accumulator\r\nreverse_tr([], Acc) ->\r\n    Acc;\r\nreverse_tr([H | T], Acc) ->\r\n    reverse_tr(T, [H | Acc]).\r\n<\/pre>\n
Lets benchmark it!<\/p>\n
\r\n1> L = lists:seq(1, 1000).\r\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n 23,24,25,26,27,28,29|...]\r\n2> mlists:bm(reverse, [L]).\r\n{33519,\r\n [1000,999,998,997,996,995,994,993,992,991,990,989,988,987,\r\n  986,985,984,983,982,981,980,979,978,977,976,975,974|...]}\r\n3> mlists:bm(reverse_tr, [L]).\r\n{64,\r\n [1000,999,998,997,996,995,994,993,992,991,990,989,988,987,\r\n  986,985,984,983,982,981,980,979,978,977,976,975,974|...]}\r\n4> L1 = lists:seq(1, 100000). \r\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n 23,24,25,26,27,28,29|...]\r\n5> mlists:bm(reverse, [L1]).  \r\n{114642276,\r\n [100000,99999,99998,99997,99996,99995,99994,99993,99992,\r\n  99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,\r\n  99981,99980,99979,99978,99977,99976,99975,99974|...]}\r\n6> mlists:bm(reverse_tr, [L1]).\r\n{3450,\r\n [100000,99999,99998,99997,99996,99995,99994,99993,99992,\r\n  99991,99990,99989,99988,99987,99986,99985,99984,99983,99982,\r\n  99981,99980,99979,99978,99977,99976,99975,99974|...]}\r\n<\/pre>\n
In this case you can notice the great performance difference between the tail and non tail recursive solutions.<\/p>\n
mlists:seq\/2<\/h5>\n
You have seen me using the lists:seq\/2<\/code> function frequently. A call to lists:seq(Argument1, Argument2)<\/code> is used to generate a list that consists of the integers from the sequence Argument1, Argument1 + 1, Argument1 + 2, .., Argument2<\/code>.<\/p>\n
\r\n% non tail recursive\r\nseq(L, H) when L > H ->\r\n    [];\r\nseq(L, H) ->\r\n    [L | seq(L + 1, H)].\r\n\r\n% tail recursive\r\nseq_tr(L, H) ->\r\n    seq_tr(L, H, []).\r\n\r\nseq_tr(L, H, Accumulator) when L > H ->\r\n    Accumulator;\r\nseq_tr(L, H, Accumulator) ->\r\n    seq_tr(L, H - 1, [H | Accumulator]).\r\n\r\n% benchmarking\r\n2> mlists:bm(seq, [1, 1000]).\r\n{187,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n3> mlists:bm(seq_tr, [1, 1000]).\r\n{160,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n4> mlists:bm(seq, [1, 10000]).  \r\n{3799,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n5> mlists:bm(seq_tr, [1, 10000]).\r\n{2676,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n6> mlists:bm(seq, [1, 100000]).  \r\n{23706,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n7> mlists:bm(seq_tr, [1, 100000]).\r\n{15528,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n<\/pre>\n
mlists:sum\/1<\/h5>\n
\r\n% non tail recursive\r\nsum([]) ->\r\n    0;\r\nsum([H | T]) when is_number(H) ->\r\n    H + sum(T).\r\n\r\n% tail recursive\r\nsum_tr(List) ->\r\n    sum_tr(List, 0).\r\n\r\nsum_tr([], Sum) ->\r\n    Sum;\r\nsum_tr([H | T], Sum) when is_number(H) ->\r\n    sum_tr(T, H + Sum).\r\n\r\n% benchmarking\r\n1> L = mlists:seq_tr(1, 10000).\r\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n 23,24,25,26,27,28,29|...]\r\n2> mlists:bm(sum, [L]).\r\n{2387,50005000}\r\n3> mlists:bm(sum_tr, [L]).\r\n{803,50005000}\r\n4> L1 = mlists:seq_tr(1, 100000).\r\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n 23,24,25,26,27,28,29|...]\r\n5> mlists:bm(sum, [L1]).         \r\n{33556,5000050000}\r\n6> mlists:bm(sum_tr, [L1]).\r\n{26847,5000050000}\r\n<\/pre>\n
mlists:average\/1<\/h5>\n
\r\n% solution using non tail recursive functions\r\naverage([]) ->\r\n    0;\r\naverage(List) ->\r\n    sum(List) \/ mlists:length(List).\r\n\r\n% solution using tail recursive functions\r\naverage_tr([]) ->\r\n    0;\r\naverage_tr(List) ->\r\n    sum_tr(List) \/ length_tr(List).\r\n\r\n% optimized tail recursive solution\r\naverage_tr1(List) ->\r\n    average_tr1(List, 0, 0).\r\n\r\naverage_tr1([], Sum, Length) ->\r\n    Sum \/ Length;\r\naverage_tr1([H | T], Sum, Length) ->\r\n    average_tr1(T, Sum + H, Length + 1).\r\n\r\n% benchmarking\r\n2> L = mlists:seq_tr(1, 100000).\r\n[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n 23,24,25,26,27,28,29|...]\r\n3> mlists:bm(average, [L]).\r\n{40654,50000.5}\r\n4> mlists:bm(average_tr, [L]).\r\n{28388,50000.5}\r\n5> mlists:bm(average_tr1, [L]).\r\n{24258,50000.5}\r\n<\/pre>\n
fib\/1<\/h5>\n
You can find a detailed post about Fibonacci sequence here<\/a>. I duplicate some results here in order to show you that, some times, converting the function to tail recursive is the only way<\/strong>.<\/p>\n
\r\n% non tail recursive\r\nfib(0) ->\r\n    0;\r\nfib(1) ->\r\n    1;\r\nfib(N) ->\r\n    fib(N-1) + fib(N-2).\r\n\r\n% tail recursive\r\nfib_tr(0) ->\r\n    0;\r\nfib_tr(1) ->\r\n    1;\r\nfib_tr(N) ->\r\n    fib_tr(0, 1, 2, N).\r\n\r\nfib_tr(L, H, C, N) when C >= N ->\r\n    L + H;\r\nfib_tr(L, H, C, N) ->\r\n    fib_tr(H, L + H, C + 1, N).\r\n\r\n% benchmarking\r\n2> timer:tc(fib, fib, [20]).\r\n{4252,6765}\r\n3> timer:tc(fib, fib_tr, [20]).\r\n{7,6765}\r\n4> timer:tc(fib, fib, [25]).   \r\n{19440,75025}\r\n5> timer:tc(fib, fib_tr, [25]).\r\n{7,75025}\r\n6> timer:tc(fib, fib_tr, [2500]).\r\n{1925,\r\n 1317090516751949629522763087125316412066606964992507141887746936727530870405038425764503130123186407746570862185871925952766836352119119528156315582632460790383834605654880612657718465632568839245978248473058179422070735553124716385450886640552392273856770672239797164264356927661308349671941673643205733343592701716715788255170679575500279186053316365583259186927359351023387298371686222860827415371443553759953659514120882763808142593366402472251348360008915585215291504984371697523871199553935714056959634778700594751875\r\n}\r\n<\/pre>\n
In this case, the difference is so huge because, apart from the lack of tail recursion, the first solution has repetition of computations. What I mean is that in order to calculate fib(5)<\/code>, for example, fib(3)<\/code> will be calculated twice (once for fib(5) = fib(4) + fib(3)<\/code> and once for fib(4) = fib(3) + fib(2)).<\/p>\n
General Recursion Examples<\/h3>\n
In the following examples I will not do conversion from non tail recursive to tail recursive.<\/p>\n
factorial\/1<\/h4>\n
\r\nfactorial(0) ->\r\n    1;\r\nfactorial(N) ->\r\n    N * factorial(N - 1).\r\n<\/pre>\n
mlists:append\/2<\/h4>\n
A call to append(List1, List2)<\/code> appends the elements from List1<\/code> to the beginning of List2<\/code>.<\/p>\n
\r\nappend([], List) ->\r\n    List;\r\nappend([H | T], List) ->\r\n    [H | append(T, List)].\r\n\r\n% examples\r\n1> mlists:append([], [7]).\r\n[7]\r\n2> mlists:append([1], [7, 11, 13]). \r\n[1,7,11,13]\r\n3> mlists:append([1, 2, 3], [7, 11, 13]).\r\n[1,2,3,7,11,13]\r\n<\/pre>\n
mlists:all\/2<\/h4>\n
all(Pred, List)<\/code> returns true<\/code> if all items belonging to the the List<\/code> return true for the predicate Pred<\/code>.<\/p>\n
\r\nall(_, []) ->\r\n    true;\r\nall(Pred, [H | T]) ->\r\n    case Pred(H) of\r\n\ttrue ->\r\n\t    all(Pred, T);\r\n\t_ ->\r\n\t    false\r\n    end.\r\n\r\n% example\r\n1> L = [1, 2, 3, 4, 5].      \r\n[1,2,3,4,5]\r\n2> mlists:all(fun(X) -> X < 6 end, L).\r\ntrue\r\n3> mlists:all(fun(X) -> X < 4 end, L).\r\nfalse\r\n<\/pre>\n
mlists:delete\/2<\/h4>\n
delete(Elem, List)<\/code> returns the List<\/code> without the first occurrence of element Elem<\/code> (if any).<\/p>\n
\r\ndelete(_, []) ->\r\n    [];\r\ndelete(Elem, [Elem | T]) ->\r\n    T;\r\ndelete(Elem, [_Elem | T]) ->\r\n    delete(Elem, T).\r\n<\/pre>\n
mlists:flatten\/1<\/h4>\n
flatten(List)<\/code> returns the flattened version of the List<\/code>.<\/p>\n
\r\nflatten([]) ->\r\n    [];\r\nflatten([[H | T] | TT]) ->\r\n    flatten([H | T ++ TT]);\r\nflatten([[] | T]) ->\r\n    flatten(T);\r\nflatten([H | T]) ->\r\n    [H | flatten(T)].\r\n\r\n% examples\r\n1> mlists:flatten([1,2,3]).\r\n[1,2,3]\r\n2> mlists:flatten([1,[2],3]).\r\n[1,2,3]\r\n3> mlists:flatten([1,[2, a, [b, ]], 3, [1, {2, [3, 6]}]]).\r\n[1,2,a,b,c,d,e,3,1,{2,[3,6]}]\r\n<\/pre>\n
Sorting<\/h4>\n
mlists:mergesort\/1<\/h5>\n
\r\nmerge([], []) ->\r\n    [];\r\nmerge(List, []) ->\r\n    List;\r\nmerge([], List) ->\r\n    List;\r\nmerge([H1 | T1], L2 = [H2 | _]) when H1 < H2 ->\r\n    [H1 | merge(T1, L2)];\r\nmerge(L1, [H2 | T2]) ->\r\n    [H2 | merge(L1, T2)].\r\n\r\nsplit(N, List) ->\r\n    split(N, List, []).\r\n\r\nsplit(0, List, List2) ->\r\n    {reverse_tr(List2), List};\r\nsplit(N, [H | T], List2) ->\r\n    split(N - 1, T, [H | List2]).\r\n    \r\nmergesort([]) ->\r\n    [];\r\nmergesort([I]) ->\r\n    [I];\r\nmergesort(List) ->\r\n    Middle = length_tr(List) div 2,\r\n    {L1, L2} = split(Middle, List),\r\n    merge(mergesort(L1), mergesort(L2)).\r\n<\/pre>\n
mlists:quicksort<\/h5>\n
\r\nsplit_pivot([]) ->\r\n    [];\r\nsplit_pivot([H | T]) ->\r\n    split_pivot(H, T, [], []).\r\n\r\nsplit_pivot(Pivot, [], Lower, Higher) ->\r\n    {Lower, Pivot, Higher};\r\nsplit_pivot(Pivot, [H | T], Lower, Higher) when H < Pivot ->\r\n    split_pivot(Pivot, T, [H | Lower], Higher);\r\nsplit_pivot(Pivot, [H | T], Lower, Higher) ->\r\n    split_pivot(Pivot, T, Lower, [H | Higher]).\r\n\r\nquicksort([]) ->\r\n    [];\r\nquicksort(List = [_ | _]) ->\r\n    {Lower, Pivot, Higher} = split_pivot(List),\r\n    append(quicksort(Lower), [Pivot | quicksort(Higher)]).\r\n\r\n<\/pre>\n
Benchmarking Merge\/Quick-sort<\/h5>\n
Worst-case performance for quicksort<\/i> is O(n2<\/sup><\/code>), while for mergesort<\/i> is O(n * log(n))<\/code>.<\/p>\n
\r\n1> L = mlists:reverse_tr(mlists:seq_tr(1, 1000)).\r\n[1000,999,998,997,996,995,994,993,992,991,990,989,988,987,\r\n 986,985,984,983,982,981,980,979,978,977,976,975,974,973,972|...]\r\n2> mlists:bm(mergesort, [L]).\r\n{5675,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n3> mlists:bm(quicksort, [L]).\r\n{65940,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n4> L1 = mlists:reverse_tr(mlists:seq_tr(1, 10000)).\r\n[10000,9999,9998,9997,9996,9995,9994,9993,9992,9991,9990,\r\n 9989,9988,9987,9986,9985,9984,9983,9982,9981,9980,9979,9978,\r\n 9977,9976,9975,9974,9973,9972|...]\r\n5> mlists:bm(mergesort, [L1]).                     \r\n{48904,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n6> mlists:bm(quicksort, [L1]).                     \r\n{6045564,\r\n [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,\r\n  23,24,25,26,27|...]}\r\n<\/pre>\n
Excercises<\/h3>\n
Try to play with the following examples. They are all simple!<\/p>\n
    \n
  1. Write the mlists:max\/1<\/code> and mlists:min\/1<\/code> function that return the max and min element of a list respectively. Then define the <\/code>mlists:mmlsa\/1<\/code> that returns the tuple {Min, Max, Length, Sum, Average}<\/code> and performs only 1 pass of the list.<\/li>\n
  2. Convert the functions factorial\/1, mlists:append\/2, and mlists:flatten\/1<\/code> to tail recursive. Benchmark them against the non tail recursive.<\/li>\n
  3. Write the function mlists:nth(N, List)<\/code> that returns the N<\/code>th element of the List<\/code>.<\/li>\n
  4. Write a non tail and a tail recursive definition for mlists:takewhile(Pred, List)<\/code> that returns the elements of the List<\/code> up till the one that returns false<\/code> when applied to Pred<\/code> (if any).<\/li>\n<\/ol>\n
    Next<\/h3>\n
    Next post will be about Erlang’s predefined modules<\/strong> and Built-in Functions (BIFs)<\/strong>.<\/p>\n","protected":false},"excerpt":{"rendered":"
    This entry is part 10 of 16 in the series Introduction to Erlang<\/a><\/div>
    Accumulators In several cases, as with the mlists:length\/1 example, the non-tail recursive function can be easily turned to a tail recursive one by using the notion of accumulator. An accumulator is an extra argument introduced to a function in order to aggregate the partial results of the function. It turns the “bottom-up” collection of the […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[40,51,28],"tags":[26,64,42],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p1ouW6-7W","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/492"}],"collection":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/comments?post=492"}],"version-history":[{"count":9,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/492\/revisions"}],"predecessor-version":[{"id":498,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/492\/revisions\/498"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=492"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}