Erlang (programming language)/Tutorials/Techniques of Recursion: Difference between revisions
imported>Eric Evers (New page: =Techniques of Recursion= ===Simple techniques=== ====Assembly-Dissasembly==== Often we would like to build a list with a recursive function. Perhaps we would like to reverse a list. W...) |
imported>Chris Day No edit summary |
||
| Line 1: | Line 1: | ||
{{subpages}} | |||
=Techniques of Recursion= | =Techniques of Recursion= | ||
Revision as of 13:27, 22 April 2008
| 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. | |||
|---|---|---|---|
|
Techniques of Recursion
Simple techniques
Assembly-Dissasembly
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 processesed as lists of chars. Syntactic sugar changes strings into lists and back. Here we use the assembly-dissassembly 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 concatination 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 right.
%%% 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 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 can not reverse a tuple of lists, because the top level stucture 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.