April 17, 2013
I’m loving Erlang, extremely powerful as I get more into it, however, it did take a bit of getting my head round, but once you start to understand function pattern matching, data guards and recursion then you are on your way.
This post is really for my own sanity, as a checkpoint if I get stuck after a period away from the language, hey – it may even help others.
What is Recursion?
Simply put, recursion is a function call to itself, it is nested so it will eventually return to the original calling point – in the order it was called – see below.
Recursion in Erlang
Take the code below:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
-module(recursion). -export([recurse/1]). recurse(Recursions) -> Agg = recurse(1,Recursions), io:fwrite("Final Result = ~w~n~n", [Agg]). recurse( Iterations, Recursions ) when Iterations =< Recursions -> io:fwrite("Iter Up~w~n", [Iterations]), UpRes = recurse( Iterations + 1, Recursions ), io:fwrite("Iter Down~w~n", [Iterations]), UpRes; recurse( Iterations, _ ) -> io:fwrite("Recursion Up End Result = ~w~n~n", [Iterations-1]), Iterations-1.
When ran gives the output:
1 2 3 4 5 6 7 8 9 10 11 12
> recursion:recurse(3). Iter Up1 Iter Up2 Iter Up3 Recursion Up End Result = 3 Iter Down3 Iter Down2 Iter Down1 Final Result = 3 ok
Lines 1 and 2 define the module and the externally accessible functions within it, the /1 simply means that for the function recurse there is at least one function with a declaration that has a single parameter.
Line 4 is the external (public) function declaration with our single parameter.
Line 5 calls the function that will use recursion. The first parameter passed i.e. (1,Recursions) initialises the Iterations variable we will use through the recursion stack (I’ll explain shortly).
Line 6 simply writes to the console a message and the number of recursions we actually did.
Line 8 is one of two versions of the recurse function with 2 parameters; this version will call itself. The important expression here is the data guard of when Iterations =< Recursions - that puts a condition that this function can only be called when that data guard expression is true. Because of this guard we need another version of the function that will execute when the data guard expression yields false – that is on line 17.
Line 9 simply writes to the console a message giving an indication of which invocation this is.
Line 11 does the recursion call, by incrementing the Iterations and also passing through how many Recursions there needs to be (that will provide our data guard as mentioned for line 8. The execution of the recurse function will pattern match against the available versions of the same function name and number of parameters. So, if the data guard expression on line 8 returns false then that function will not match so another will be searched for, the only other one has the declaration (line 17) that will match so that will get executed.
Line 13 simply writes where we are to the console.
Line 15 returns a result.
Line 17 is another function declaration for the 2 parameter recurse function, the underscore i.e. _ simply indicates we aren’t interested in that parameter, if we could not do that we’d need to put a variable in there, it would be a variable we never use and you’d get a warning at compile time.
Line 18 writes to the console.
Line 19 returns a result.