{"id":485,"date":"2011-03-30T20:11:35","date_gmt":"2011-03-30T19:11:35","guid":{"rendered":"http:\/\/trigonakis.com\/blog\/?p=485"},"modified":"2011-04-19T08:43:47","modified_gmt":"2011-04-19T07:43:47","slug":"introduction-to-erlang-recursion-12","status":"publish","type":"post","link":"http:\/\/trigonakis.com\/blog\/2011\/03\/30\/introduction-to-erlang-recursion-12\/","title":{"rendered":"Introduction to Erlang : Recursion (1\/2)"},"content":{"rendered":"
This entry is part 9 of 16 in the series Introduction to Erlang<\/a><\/div>

Recursion<\/h3>\n

The definition of the word recursion<\/i> is “(mathematics) an expression such that each term is generated by repeating a particular mathematical operation”, according to the WordNet<\/i>. Recursion is one of the most powerful “tools” in a functional programming language and so it is for Erlang. Recursion can be used to apply divide and conquer<\/i> techniques to problem solving, where a problem is broken to smaller subproblems, the subproblems are solved, and the results are “merged” to generate the final result.<\/p>\n

Recursion happens when a function’s body definition includes a call to the function itself.<\/p>\n

\r\nfunctionA(...) ->\r\n    Body_before_recursion, % optional\r\n    functionA(...),\r\n    Body_after_recursion. % optional\r\n<\/pre>\n
Recursion is used instead of the conventional loop statements of other programming languages, such as while<\/code> and for<\/code> in C.
\n<\/p>\n
Examples<\/h4>\n
mlists:is_list\/1<\/h5>\n
This is a Prolog-like definition of a function that checks if a construct is a list:<\/p>\n
\r\nis_list([]) -> % the empty list is a list\r\n    true;\r\nis_list([_ | T]) ->\r\n    mlists:is_list(T); % a compound construct is a list if it consinsts of\r\n                       % a head and tail that has to be a list\r\nis_list(_) ->\r\n    false.\r\n\r\nis_list2([]) -> % a more Erlang-friendly definition\r\n    true;\r\nis_list2([_ | _]) ->\r\n    true;\r\nis_list2(_) ->\r\n    false.\r\n<\/pre>\n
mlists:length\/1<\/h5>\n
This function calculates the lenght of a list:<\/p>\n
\r\nlength([]) ->\r\n    0;\r\nlength([_ | T]) ->\r\n    1 + mlists:length(T).\r\n\r\n% an optimized version or length\/1\r\nlength1([]) ->\r\n    0;\r\nlength1([_, _, _ | T]) ->\r\n    3 + length1(T);\r\nlength1([_ | T]) ->\r\n    1 + length1(T).\r\n<\/pre>\n
Pretty simple, right? Lets measure the performance of mlists:length\/1<\/code> and length1\/1<\/code>. For this purpose we will use a very useful BIF (Built-In Function); the timer:tc\/3<\/code>. This function can be used as:<\/p>\n
\r\n% Module & Fuction : atoms\r\n% Parameters : list\r\n% returns: {TimeInMicroSeconds, Result}\r\ntimer:tc(Module, Function, Parameters).\r\n<\/pre>\n
Using it we get:<\/p>\n
\r\n1> L = 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\n2> timer:tc(mlists, length, [L]).\r\n{10864,100000}\r\n3> timer:tc(mlists, length1, [L]).\r\n{2165,100000}\r\n4> L1 = lists:seq(1, 100).        \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> timer:tc(mlists, length, [L1]).\r\n{11,100}\r\n6> timer:tc(mlists, length1, [L1]).\r\n{4,100}\r\n<\/pre>\n
Notice how a simple “trick”, consuming more than one element at a time, improves the performance.<\/p>\n
for\/1<\/h5>\n
The following function implements a construct similar to a for<\/code> loop using higher level functions.<\/p>\n
\r\nfor(I, Condition, Increase, Do, Data) ->\r\n    case erlang:apply(Condition, [I]) of\r\n\ttrue ->\r\n\t    DataNew = erlang:apply(Do, [I, Data]),\r\n\t    INew = erlang:apply(Increase, [I]),\r\n\t    for(INew, Condition, Increase, Do, DataNew);\r\n\t_ ->\r\n\t    Data\r\n    end.\r\n<\/pre>\n
And can be used as:<\/p>\n
\r\n2> I = 0, Condition = fun(J) -> J < 10 end.\r\n#Fun\r\n3> Increase = fun(J) -> J + 1 end.\r\n#Fun\r\n4> Do = fun(J, D) -> [J | D] end.\r\n#Fun<\/erl_eval>\r\n5> Data = [].\r\n[]\r\n6> loop:for(I, Condition, Increase, Do, Data).\r\n[9,8,7,6,5,4,3,2,1,0]\r\n7> f(). % can be used to forget the existing binding,\r\n        % use f\/1 as f(Binding) to forget a specific binding\r\nok\r\n8> I = [a, b, c, d], Condition = fun(J) -> J =\/= [] end.\r\n#Fun<\/erl_eval>\r\n9> Increase = fun(J) -> [_H | T] = J, T end.\r\n#Fun<\/erl_eval>\r\n10> Do = fun(J, D) -> {J, D} end.\r\n#Fun<\/erl_eval>\r\n11> Data = {}.\r\n{}\r\n12> loop:for(I, Condition, Increase, Do, Data).          \r\n{[d],{[\/c],{[b,c,d],{[a,b,c,d],{}}}}}\r\n<\/erl_eval><\/pre>\n
fib\/1<\/h5>\n
Fibonacci of course!<\/p>\n
\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<\/pre>\n
Tail Recursion<\/h4>\n
A function is called tail recursive<\/i> when the recursive call to itself happens only in the last expression of the body in every clause. So,<\/p>\n
\r\nnon_tail_recursive(...) ->\r\n    non_tail_recursive(...),    \r\n    other_expression,\r\n    ... .\r\n\r\ntail_recursive(...) ->\r\n    other_expression,\r\n    ...     \r\n    tail_recursive(...).\r\n<\/pre>\n
the first function is not tail recursive because the recursive call is followed by other expressions, while the second is, since the recursive call is the last statement.<\/p>\n
Tail Recursion & Performance<\/h5>\n
In many programming languages tail recursion is good approach performance wise. In general, this is not the case in the latest releases of Erlang. Tail recursion is not guaranteed to give you better performance. This fact is even stated in  the Efficiency Guide<\/i> in Erlang documentation, as one of the “myths” about Erlang’s performance.<\/p>\n
The proper way to evaluate performance is by benchmarking!<\/p>\n
Tail vs. No Tail Recursive example<\/h6>\n
A tail recursive mlists:length_tr\/1<\/code>:<\/p>\n
\r\n% not tail recursive\r\nlength([]) ->\r\n    0;\r\nlength([_ | T]) ->\r\n    1 + mlists:length(T).\r\n\r\n% tail recursive\r\nlength_tr(List) ->\r\n    length_tr(List, 0).\r\n\r\nlength_tr([], Length) ->\r\n    Length;\r\nlength_tr([_ | T], Length) ->\r\n    length_tr(T, Length + 1).\r\n<\/pre>\n
And the benchmarking:<\/p>\n
\r\n2> L = 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\n3> timer:tc(mlists, length, [L]).\r\n{9538,100000}\r\n4> timer:tc(mlists, length_tr, [L]).\r\n{6421,100000}\r\n5> L1 = lists:seq(1, 100).\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\n6> timer:tc(mlists, length, [L1]).  \r\n{21,100}\r\n7> timer:tc(mlists, length_tr, [L1]). \r\n{9,100}\r\n8> L2 = lists:seq(1, 1000000).       \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\n9> timer:tc(mlists, length, [L2]).   \r\n{126760,1000000}\r\n10> timer:tc(mlists, length_tr, [L2]). \r\n{32865,1000000}\r\n11> L3 = lists:seq(1, 10000000).                              \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\n12> timer:tc(mlists, length, [L3]).       \r\n{1262031,10000000}\r\n13> timer:tc(mlists, length_tr, [L3]).\r\n{286848,10000000}\r\n<\/pre>\n
Which reveals that in this case the tail recursive solution is quite faster than the non-tail recursive! The followed technique for transforming a function to tail recursive is very common and quite usefull and thus will be discussed in the next post.<\/p>\n
Tail Recursion & Memory Leaks<\/h5>\n
Try running the explode\/0<\/code> function:<\/p>\n
\r\nnothing() ->\r\n    nothing.\r\n\r\nexplode() ->\r\n    explode(),\r\n    nothing().\r\n<\/pre>\n
After some time you will get the following output:<\/p>\n
\r\n11> loop:explode().\r\n\r\nCrash dump was written to: erl_crash.dump\r\neheap_alloc: Cannot allocate 1140328500 bytes of memory (of type \"heap\").\r\nAborted\r\n<\/pre>\n
The reason why this happened is simple and should be obvious to most of you. Every call to explode\/1<\/code> makes a new call, while the current one has not yet finished (non tail recursive -> something has to run after the recursive call returns) and so the space in the call stack<\/i> cannot be freed for the current call until the next call returns. This never happens though, so eventually the runtime cannot allocate the memory space needed for creating a new call stack entry and crashes!<\/p>\n
Next<\/h3>\n
I will break this post here cause it is already quite long and I still have many things to write! So the next post will be also about recursion. I will present more examples and, for the first time, I will include some small programming excercises :-).<\/p>\n","protected":false},"excerpt":{"rendered":"
This entry is part 9 of 16 in the series Introduction to Erlang<\/a><\/div>
Recursion The definition of the word recursion is “(mathematics) an expression such that each term is generated by repeating a particular mathematical operation”, according to the WordNet. Recursion is one of the most powerful “tools” in a functional programming language and so it is for Erlang. Recursion can be used to apply divide and conquer […]<\/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-7P","_links":{"self":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/485"}],"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=485"}],"version-history":[{"count":11,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/485\/revisions"}],"predecessor-version":[{"id":545,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/posts\/485\/revisions\/545"}],"wp:attachment":[{"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/media?parent=485"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/categories?post=485"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/trigonakis.com\/blog\/wp-json\/wp\/v2\/tags?post=485"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}