Some months ago Kevin (check him out at Hypothetical Labs) started the RDU erlounge, a monthly meeting of area erlang enthusiasts. The meetings were organized via a mailing list. Recently one of the guys on the list, Jared (Alloy Code), asked for a bit of help. He was working an exercise (a function to compute the least element in a list of integers) and trying to get his head around recursion. I offered to help, and the resultant emails have morphed into this post.
Here’s Jared’s comment:
Hi David, Thanks for the offer! 2008 marks the 10 year anniversary of the first time I was exposed to recursive functions, and sadly, I still have some trouble following the execution path when the recursion triggers more than a handful of times. I’ve tried to plot this out on paper, and I can’t seem to follow the recursion properly. The function returns the expected result, but I’m kind of at a loss as to why. As near as I can tell, this code is working in spite of itself. Also, I’m not sure using the guard for length(T) is the proper way to prevent recursing into an empty list…
min([H|T]) when length(T) > 0 -> case H < min(T) of true -> H; false -> min(T) end; min([H|T]) when length(T) =:= 0 -> H.Regards, Jared
Jared,
You ask whether “the guard for length(T) is the proper way to prevent recursing into an empty list”. No, it’s not. Pattern matching is the idiomatic way. Typically, a recursive function is written in two clauses: one is used to terminate the recursion, the other handles the general case. Pattern matching on the argument is used to dispatch the appropriate clause. For instance:
min([X]) -> X; min([X | Y]) -> smaller(X, min(Y)). smaller(X,Y) when X > Y -> Y; smaller(X, _) -> X.
The first line says that the min of a single element list is the single element. This handles termination of the recursion. The next clause handles the general case.
Notice one fine point: the order in which the the two clauses which make up min are written matters. The rule of thumb is to put the clause matching the more specific pattern first. If you swapped the order of the two min clauses, the second would never be executed. Try it and see what happens; it is worth understanding.
The smaller function just compares two elements. Again, the order of the two clauses in smaller matters.
Understanding how this version of min works is easy, once you get your head around it. Consider a specific list A = [2,1,3], and follow the substitutions:
min([2, 1, 3] ) %%---here X is 2, Y is [1,3] smaller(2, min([1,3]) smaller(2, smaller(1, min([3]))) %%--- min([3]) is just 3 smaller(2, smaller(1, 3)) smaller(2, 1) 1
Note that this is a way to think about how recursion works, not an an explanation of how erlang actually implements recursion.
A good book to help get your head around recursion is The Little Schemer. Yeah, it is in scheme, but scheme syntax is both simple and elegant. This is a top notch book whose purpose is to teach the reader to think recursively. Also useful, and freely available online, are the early chapters of Structure and Interpretation of Computer Programs. SICP is another scheme book, and is one of the classics of computer science.
One weakness of this example is that min is very easy to compute imperatively using a loop. One might be left wondering what is the big deal about recursion. This blog (much neglected recently) has a couple of examples of how recursion can make short work of a problem not so easily handled by looping, for instance, this one.
Posts
I wouldn’t call that fully idiomatic of “good” recursion because it is not tail recursive, so a list of 100,000 elements would have a stack 100,000 function calls deep. The whole discussion of using another argument to flatten out recursion has to then ensue.
Note that this example is extemporaneous, so it may be buggy (I don’t have erlang here to test this. (Note that I use ‘ok’ and ‘error’ for example error checking as well)
[code]
% Empty lists are bad, there is no minimum to no-value/NULL
min([]) -> {error, []};
% A simple identity operation for completeness
min({ok, X}) -> {ok, X};
% A well defined entry point, e.g. the “normal” case
min([H|T]) -> min({ok, H},T).
% fixed point of recursion, list is empty, the answer is B
min({ok,B},[]) -> {ok,B};
% the only test in the whole module, the guard selects the new minimum value here
min({ok,B},[H|T]) when B > H -> min({ok,H},T);
% By default the old B is less than the head, so we don’t care about it any more
min({ok,B},[_H|T]) -> min({ok,B},T).
% helper for doing “X = 5 * value(min(List))” and (drop ‘ok’ after check, return V)
value({ok,V}) -> V.
[/code]
Note that since the very last call in every branch that recurses, a call to the recursion, the compiler is free to not save up intermediate values in a call stack they way it would have to in the case of smaller(H,min(T)) since in that case min is evaluated to return a value before smaller can be called [arguments evaluate first].
So we use matching _and_ guards as the mechanism to do recursion “right” where matching is primary, but guards disambiguate “identical” matches, so fn(X) is unambiguous where things like fn(X,Y) and another fn(X,Y) must rely on guarding.
As a general rule, you should: Match before Guard, Guard before Test-with-if/case.
August 1, 2008 @ 4:09 pm
re: iteration vs. recursion
recursion in Erlang works hand in hand with single-assignment variables, no?
August 7, 2008 @ 4:22 pm