Re: Recursion

[mfb@mbunix.mitre.org (Michael F Brenner)]

A recursive definition of the positive integers which contain only
the digits 3, 5, and 9 is (3*5*9*)*, where * means repeat the prior
expression zero or more times. One some email systems the stars
will not be correctly displayed as superscripts, in which case,
image they are raise up a little, like exponents.

To learn how to do things like this try reading Epstein: Word Processing
in Groups. This is covered in chapter 1.

Before seeing is your code for adding up a list is recursive, 
(and before making it recursive in the sense your instructor
desires) it might be a good idea to put in the preconditions and
set it up as an encapsulated limited private type.

The first step could be to give it the following package spec.

generic
  type values  is limited private;
  type indexes is private;
package list_manager is
  type lists is private;
  procedure initialize (list: in out lists);
  procedure finalize   (list: in out lists);
  procedure insert     (list: in out lists; after: indexes: value: values);
  procedure delete     (list: in out lists; index: indexes);
  function  next       (list: lists; index: indexes) return indexes;
  function  prior      (list: lists; index: indexes) return indexes;
  function  home       (list: lists) return indexes;
  function  value      (list: lists; index: indexes) return values;
  procedure set_value  (lists: in out lists; index: indexes; value: values);
end list_manager;

Using a visible part (spec) like this will hide (encapsulate) the
data structure from your program part, so will not directly
access the definition of the list. Therefore, instead of 
      list := list.next

you would use something like

      current := list_manager.next (list, current);

This has the disadvantage of having a few extra keystrokes, but the
advantage that you can change the representation of your code. The
thing this gives you is often project success. For example, you
could write a package body that uses a fixed length array to 
completely test out your linked list. After you having it working
on a simple array, you could test it out on a non-recursive list
algorithm. Finally, you could test is out on a recursive list 
algorithm.

Changing to the form your instructor desires is not the hard part,
the hard part is getting it to work properly.

To find out about preconditions, there are many computer science
texts on the market, but Dijkstra, The Discipline of Programming
comes to mind.

Mike