Recursion

Recursion

[Dirien B. Perez]

Hi I am having some problems with recursion I have the iterative 
version of a function that will calculate the sum of the elements is a
linked list:

	function sum(list:cell_ptr) return integer is
	local:cell_ptr:=list;
	s:integer:=0;
	begin
		while local /= null loop	
		s:=s+local.value;
		local:=local.next
		end loop;
	return s;
	end sum;
I need help creating the recursion version. Also I need to createa
recursive definition of the set of all positive numbers containing only
the digits 3,5 and 9.

I appreciate any help that I can get...... and thank you in advance.
future ada programmer..

Re: Recursion

[Larry Coon]

Dirien B. Perez wrote:

> Hi I am having some problems with recursion I have the iterative
> version of a function that will calculate the sum of the elements is a
> linked list:
> 
>         function sum(list:cell_ptr) return integer is
>         local:cell_ptr:=list;
>         s:integer:=0;
>         begin
>                 while local /= null loop
>                 s:=s+local.value;
>                 local:=local.next
>                 end loop;
>         return s;
>         end sum;
> I need help creating the recursion version.

I don't want to do your homework for you (I'm assuming
that's what this is for), but it should be something like:

function sum (current_cell: cell_ptr) return int is
	if current_cell.next = null then
		return 1;
	else
		return sum (current_cell.next) + 1;
	end if;
end sum;

I'll leave it to you to modify this to correctly
distinguish an empty linked list from one with a single
item.  I'll also leave it to you to extrapolate from
this problem to your other problem.

Larry Coon
University of California
larry@fs2.assist.uci.edu
and lmcoon@home.com

Re: Recursion

[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