TEACH POPCOURSE8 - Recursion and tracing

Contents

Recursion

Using the `matches' command we can easily split a list into different parts. In particular we can dig out the first element and the list of all remaining elements by matching the list against a pattern that has a single-query variable in the first position and a double-query variable in the second. Here is an example.

vars num other_nums;
if [one two three four five] matches [?num ??other_nums] then
   num ==>
   other_nums ==>
endif;

** one
** [two three four five]
Technically, the first element of a list is known as the `head'. The list of remaining elements is known as the `tail'. And there are in fact built-in procedures that extract the head and tail of a list. The built-in procedure `hd' extracts the head. The built-in procedure `tl' extracts the tail. Thus

hd(nums) ==>
** one
tl(nums) ==>
** [two three four five]
Being able to split a list into its head and its tail opens up a new way of writing certain types of procedure. We can illustrate this with the following definition of a procedure that adds up all the numbers in a list.

define addup(list) -> total;
   if list = [] then
      0 -> total;
   else
      hd(list) + addup(tl(list)) -> total;
   endif;
enddefine;
The weird thing about this procedure is that it calls itself! (See the middle part of the fifth line.) But concentrate to begin with on the parts that are easy to understand. Note how the condition in the `if' checks whether the input `list' is empty and assigns 0 to `total' if it is. This means that if we call the procedure with an empty list it will certainly return 0.

addup([]) ==>
** 0
But if we call the procedure with a list of at least one element then the condition `list = []' will not be satisfied. This means that the `else' part of the `if' will be executed. This contains a single command which adds the first item of the list to the result of applying the `addup' procedure to the tail of the list. As we noted, this is rather strange since the procedure is effectively calling itself as a subroutine. But it turns out to be a perfectly valid approach. And it does work!

addup([3]) ==>
** 3
Because the tail of the list is empty, the result produced when `addup' calls itself is just 0 (see the explanation above). So the `+' just adds 3 (the first element of the list) to 0 to produce 3. This is assigned to the output variable `total' and becomes the final result of the original call.

Whenever the procedure is given a non-empty list, it always ends up adding the head of the list to the result of calling `addup' on the tail. Because we know that `addup' will get the answer right when given an empty list we know that it must get the answer right when given a list of one element. And if it gets the answer right when given a list of one element, it must get it right when given a list of two elements. And if it gets the answer right when given a list of two elements, it must get it right when given a list of three elements. And so on. We can test it out by giving it a list of eight elements.

addup([34 522 8766 12 14 2 0 8]) ==>
** 9358
Experiment: load the definition given above and then test it out on a list of your own.

Reversing a list recursively

Procedures that call themselves are said to be `recursive'. We can write recursive procedures for all sorts of purposes. In particular we can write procedures that do list manipulation, i.e. procedures that take a list and rebuild it in a new way. A simple example of this is a procedure that reverses a list. (Note that POP-11 actually has a built-in procedure for doing this called `rev'.)

As is often the case, the task of reversing a list is most easily accomplished by building up a new list, repeatedly adding in elements to a new list that is initially empty. (This involves using hats and double hats to add new items to an existing list.) A procedure to do this the usual way (using a looping command) might be defined as follows.

define reverse(list) -> newlist;
   vars item;
   [] -> newlist;
   for i from 1 to length(list) do
      list(i) -> item;
      [^item ^^newlist] -> newlist;
   endfor;
enddefine;
This works OK.

reverse([1 2 3]) ==>
** [3 2 1]
But a recursive definition of the `reverse' procedure might look like this.

define reverse(list) -> new_list;
   vars x rest, reversed_rest;
   if list matches [?x ??rest] then
      reverse(rest) -> reversed_rest;
      [^^reversed_rest ^x] -> new_list;
   else
      [] -> new_list;
   endif;
enddefine;
The procedure contains a `vars' command and a single `if'. The `vars' sets up two variables: `x' and `rest'. The condition in the `if' is that the value of `list' must match the pattern [?x ??rest]. If `list' matches ok then we will have the first element in the variable `x' and the remaining elements (as a list) in `rest'. With these two components the procedure can construct the reverse of the whole list by a recursive step. First it gets the reverse of the `rest' and puts it into the variable `reversed_rest'. Then it tacks `x' on to the end of this by building a new list with `reversed_rest' merged in at the beginning and the value of `x' inserted at the end.

If the list does not match the pattern, then it has to be an empty list. And in this case, it is just an empty list that should be returned. (The reverse of an empty list is just an empty list.)

The confusing thing about all this is that the procedure obtains the reverse of `rest' by calling itself. But everything works out fine. POP-11 keeps each call of a particular procedure entirely separate. So there is no interference whatsoever between two calls of the same procedure. The `list' variable of the original call is completely separate from the `list' variable in the new call. They are effectively two different variables. Ditto for the other two local variables in the procedure: `x' and `rest'. Thus there is no interference between the different calls of the procedure, even when the call is executed by the procedure itself.

Due to the way `reverse' calls itself with the tail of the list passed in, the original list gradually gets broken down until eventually we just have an empty list left. The reverse of an empty list is just an empty list, and this is indeed the value produced when an empty list is passed in to `reverse'.

Using the `trace' command to show procedure calls

Recursive processes such as the one described above can be mind-boggling. We can get some help from POP-11 by using the `trace' command. This command tells POP-11 to print out information showing when a procedure call is made, and what the values of the input and output variables are. This information can be particular helpful for illustrating how a recursive procedure words.

The `reverse' procedure can be used to demonstrate the effect. First we execute the `trace' command by typing the word `trace' followed by the name of the procedure we are interested in.

trace reverse;
This command is a statement: it produces no value---it just tells POP-11 to print information whenever `reverse' is called. The result is that calling reverse now generates a lot of extra printing.

reverse([1 2 3 4]) ==>
> reverse [1 2 3 4]
!> reverse [2 3 4]
!!> reverse [3 4]
!!!> reverse [4]
!!!!> reverse []
!!!!< reverse []
!!!< reverse [4]
!!< reverse [4 3]
!< reverse [4 3 2]
< reverse [4 3 2 1]
** [4 3 2 1]
Everything here except the final line (the one beginning with `**') is `trace printing'. The first line after the original call begins with `> reverse'. This is POP-11 telling us that there has been a call on `reverse' and that it is therefore entering the procedure. After the word `reverse' we see `[1 2 3 4]'. This is the list-value passed-in as an argument.

The next line is almost the same except that it begins with `!> reverse' and ends with `[2 3 4]'. This information tells us that there has been a new call on `reverse'. The single exclamation mark tells us that the call has been made within a previous call of a traced procedure. Thus we are one level `deep'. Because the `reverse' procedure chops off and applies a recursive call to the tail of the list the input variable value is shown as `[2 3 4]'.

And so it continues all the way down until a call is issued in which the input variable has the value [ ]. At this point no further recursive calls are issued. The value returned by the procedure is just the value that was passed in, i.e., [ ]. The process then unwinds with each call tacking the head that it extracted to the end of the value it gets back from the recursive call. When the original call exits, we have the list in reverse form.

Experiment: take a few minutes to study the trace printing for the call on `reverse'. Once you have everything clear, apply the `trace' command to the `addup' procedure defined above; i.e., do

trace addup;
Then call `addup' on a list of your own choosing and see what trace printing is produced. Once you are quite certain you have understood the way recursive procedures work, you can move on to do the exercises below.

Tip of the day

It is possible to send a complete ved file by email simply by giving the Ved command `send emailname'. For example, to send a file to me give the command `send christ@cogs.susx.ac.uk'.

Exercises

To test your knowledge of the material presented in this file you should do the following exercises. First, copy them into a file of your own. Then, edit in answers underneath each question (copying in any relevant output from your output file) and print out the file.

  1. Write a procedure called `ismember'. This should take a single value and a list and then return <true> if the value is contained and the list and <false> otherwise. (Remember that <true> and <false> are just the values of the built-in variables `true' and `false'.) The procedure should work recursively and produce exactly the same behaviour as the built-in `member' procedure.

  2. Show what trace output is produced if you trace `ismember' and call it as follows: `ismember(4, [8 7 6 5 4 3]) ==>'

  3. Write a procedure called `extract' that takes a single value and a list and effectively deletes every occurrence of that value. The procedure should actually do this by recursively reconstructing the list from the elements of the original list.

  4. Write a procedure called `get_usages'. This should take a list of `phone-usages' (i.e., sublists giving a name, a time in minutes, and a charge rate) and return a list identifying the current phone-bill for each phone user. It should behave like this

    get_usages([[Freda 25 0.1][Jacky 2  0.2][Jacky 1  0.2][Freda 8 0.15]]) ==>
** [[Jacky 0.6] [Freda 3.7]]
    Note that the procedure should not make any assumptions about the names appearing in the list. (Hint: you may find it easier to first write a procedure `get_usage_for(name)' and then use this as a subroutine.)

  5. Write a procedure called `get_biggest_usage' that takes a list of usages (such as is returned by the `get_usages' procedure) and returns the sublist associated with the biggest usage. It should behave like this

    get_biggest_usage([[Jacky 0.6] [Freda 3.7][Bill 1.2]]) ==>
** [Freda 3.7]
  6. Write a procedure called `sorted_users'. This should take a phone-calls database and return a sorted list of users. The name of the person who has the largest total costs should appear first in the list, the name of the person with the second largest costs second, and so on. The procedure should make not make any assumptions about the names that appear in the database. It should make use of your `extract', `get_usages' and `get_biggest_usage' procedures. (Hint: one way to produce a sorted list from an unsorted list is to repeatedly extract the biggest element from the list, adding it (each time) to the end of a new list.) Use trace printing to show the way in which your procedures call each other.

Quick reference

These are the commands introduced in this file.

trace      tells POP-11 to display calls of specified procedure(s)
rev        built-in procedure that reverses a list

Moving on

If you have completed all the exercises successfully, you are ready to move on to TEACH POPCOURSE9.

Page created on: Fri Apr 26 09:34:58 BST 2002
Feedback to Chris Thornton
hits this year