Erlang (programming language)/Tutorials/Techniques of Recursion

The metadata subpage is missing. You can start it via filling in this form or by following the instructions that come up after clicking on the [show] link to the right.

Do you see this on PREVIEW? then SAVE! before following a link. To find out more about the use of metadata for the management of Citizendium pages, see CZ:Metadata. You may see this box for one of two reasons. Either: A - New page has been created, or subpages template was added to an existing page B - Cluster move is in progress Click either the A or B link for further instructions. [Feel free to recommend improvements to the text or links in this template] A - For a New Cluster use the following directions Subpages format requires a metadata page. Using the following instructions will complete the process of creating this article's subpages. Click the blue "metadata template" link below to create the page. On the edit page that appears paste in the article's title across from "pagename =". You might also fill out the checklist part of the form. Ignore the rest. For background, see Using the Subpages template Don't worry--you'll get the hang of it right away. Remember to hit Save! the "metadata template". However, you can create articles without subpages. Just delete the {{subpages}} template from the top of this page and this prompt will disappear. :) Don't feel obligated to use subpages, it's more important that you write sentences, which you can always do without writing fancy code. [Feel free to recommend improvements to the text or links in this template] B - For a Cluster Move use the following directions The metadata template should be moved to the new name as the first step. Please revert this move and start by using the Move Cluster link at the top left of the talk page. The name prior to this move can be found at the following link. [Feel free to recommend improvements to the text or links in this template]

---

Techniques of Recursion

Simple techniques

Assembly-Disassembly

This section explains the technique of using accumulator variables in auxiliary functions.

An accumulator variable is a place to build some result. An auxiliary function is a hidden function that sometimes uses an accumulator variable.

Often we would like to build a list with 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 then 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. Remember, we need to bracket H because it needs to be a list when we do list concatenation with the plus-plus, '++'. The tail, T, in [H|T] is always a list. H may or may not be a list in [H|T]; either way we need to give H a bracket so [H] is always a list. List ++ [H] must produce a list.

%%% 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-dissasembly method
                                 %%   of recursion.
                                 %% reverse(L1,L2) is the private version of reverse
reverse( [], Build) ->           %% The base case: has an emtpy list for input so
    Build;                       %%   we are done building and return the finished answer: Build
reverse( [H|T], Build) ->        %% The recursive case: has at least one element: H 
    reverse( T, [H] ++ Build ).  %%   so glue H 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 can not 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, do the reverse then change it back to a tuple on the way out.

Exercises

1) Write a function t_reverse(T) that reverses a Tuple, T.

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.