Erlang Programming/Techniques of Recursion

Techniques of Recursion

Simple techniques

Assembly-Disassembly

Often we would like to build a list using a recursive function. Perhaps we would like to reverse a list. We start with a single-argument version (the public entry point function) and use it to call the double-argument version (private), where the extra argument contains the output we wish to build. We can take the head off of the input, [H|T], as we build up the output, Build. When input is empty, we are done.

Observe the nice way that strings are actually processed as lists of chars. Syntactic sugar changes strings into lists and back.

(Here we use the assembly-disassembly technique of recursion. Johnny-Five would not approve of this technique. [Reference to the 1986 movie "Short Circuit."])

Remember, we need to bracket H because it needs to be a list when we do list concatenation with the plus-plus, '++'. T is always a list in [H|T]. H may or may not be a list in [H|T]; either way we need to give it a bracket so it behaves properly.

%%% provides utility functions
                                 %
-module(util).                   
-export([reverse/1]).
                                 %% reverse(L) is for public use
                                 %%   RETURNS: the reverse of a list L
                                 %%   ARG: L <== any list 
reverse( L ) ->                  %% The entry point function: reverse(L) 
    reverse( L, []).             %%   the private function: reverse(L1, L2)
                                 %%
                                 %% reverse() uses the assembly-disassembly method
                                 %%   of recursion.
                                 %% reverse(L1,L2) is the private version of reverse
reverse([], Build) ->            %% The base case: has an empty list for input so
    Build;                       %%   we're done building and return the final answer: Build
reverse([H|T], Build) ->         %% The recursive case: has at least one element: H 
    reverse( T, [H] ++ Build ).  %%   so glue it onto Build and 
                                 %%   recurse with the left-overs: T

% sample output
                                                                      %
c(util).            
  {ok,util}
                                                                      %
util:reverse("abc").
  "cba"
                                                                      %
util:reverse([1,2,3]).
  [3,2,1]
                                                                      %
util:reverse( [ [1,1], [2,2], [3,3]]).
  [ [3,3], [2,2], [1,1]]
                                                                      %
util:reverse([ {1,1}, {2,2}, {3,3} ]).
  [ {3,3}, {2,2}, {1,1} ]
                                                                      %
util:reverse( { [1,1], [2,2], [3,3] } ).
  error

Compile and run.

We can reverse a string, which is really a list. We can reverse a list of integers. We can reverse a list of lists. We can reverse a list of tuples. But we cannot reverse a tuple of lists, because the top level structure is not a list.

If we wanted to be slick, we could use a guard to check the type of the argument at the entry point, then if it is a tuple, change it to a list, execute the reverse, and then change it back to a tuple on the way out.

Please note that the example is purely educational, and in real applications you should avoid appending to the list one element at a time. The correct way to build a list is using the [Head|Tail] form. Often this will cause the list to be in reverse order. To remedy that we then use the lists:reverse built-in-function. See example

%slow
build_append()->build_append(0,[]).
build_append(N,L) when N < 100000 -> build_append(N+1,L++[N]);  % function calls its self with N+1 and a new list with N as the last element.
build_append(_,L) -> L.

%fast
build_insert()->build_insert(0,[]).
build_insert(N,L) when N < 100000 -> build_insert(N+1,[N|L]);   % function calls its self with N+1 and a new list with N as the head.
build_insert(_,L) -> lists:reverse(L).                          % function has to reverse the list before it retuns it.

Compile and run the functions to compare.

The reason behind the speed difference is in the implementation of Erlang lists as linked lists.

Exercises

1) Write a function t_reverse(T) that reverses a Tuple, T, of size 5. (i.e. {a,b,c,d,e})

2) Write a function r_reverse(L) that recursively reverses each sublist in a list of lists, L.

3) Write a function s_reverse(L) that recursively reverses only the sublists but not the top level in a list of lists.

4) Write a function n_reverse(L) that recursively reverses sublists only if they contain integers.