* Recursion
@ 1997-10-06 0:00 Dirien B. Perez
1997-10-06 0:00 ` Recursion Larry Coon
1997-10-09 0:00 ` Recursion Michael F Brenner
0 siblings, 2 replies; 3+ messages in thread
From: Dirien B. Perez @ 1997-10-06 0:00 UTC (permalink / raw)
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..
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Recursion
1997-10-06 0:00 Recursion Dirien B. Perez
@ 1997-10-06 0:00 ` Larry Coon
1997-10-09 0:00 ` Recursion Michael F Brenner
1 sibling, 0 replies; 3+ messages in thread
From: Larry Coon @ 1997-10-06 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Recursion
1997-10-06 0:00 Recursion Dirien B. Perez
1997-10-06 0:00 ` Recursion Larry Coon
@ 1997-10-09 0:00 ` Michael F Brenner
1 sibling, 0 replies; 3+ messages in thread
From: Michael F Brenner @ 1997-10-09 0:00 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~1997-10-09 0:00 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1997-10-06 0:00 Recursion Dirien B. Perez
1997-10-06 0:00 ` Recursion Larry Coon
1997-10-09 0:00 ` Recursion Michael F Brenner
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox