Lecture 20 - October 31, 2007

We went over the homework you did for today: Page 7 of the exam AND a description of what puzzle.adb (from last class) did. We discussed the descriptions written.

I handed out printouts of the results of running your linked list specifications and bodies with my test program. A number of you had programs that wouldn't compile because you left out one of the functions in the original specification. Also, none of you had user defined exceptions. You have until Friday around noon to correct your programs and re-submit them electronically. A description of what to submit is available on Blackboard.

More on Recursion

Typical examples:

n!

addition

searching an array

Fibonacci numbers

traversing a tree in reverse order

combinations

towers of Hanoi

traversing a tree

recursive binary search

When dealing with recursion, you need to make sure you have a base or stopping case.

You need to make sure that your problem space is getting smaller (i.e. closer to the base case.

It is okay to have multiple return statement in a recursive solution.

Further discussion about the Josephus problem.

Instead of killing people, the elements in our CLIST are fruits and we will be making fruit salad by adding the fruits one at a time.

Ask the USER: What is the first fruit you want to add to the salad (i.e. remove from the CLIST?

Tell the USER: Give me a number in the range ___ to ___ that tells me how far along the CLIST to go to find the subsequent fruit to add to the salad.

This variant of the Josephus problem is up on Blackboard and is due Monday along with your altered sorting programs.

A question was asked about the number associated with each element of an

enumerated type. Program testenum.adb on the next page illustrates use of 'POS and 'VAL

with ada.integer_text_io;

with ada.text_io;

procedure testenum is

type monkey is (spider, howler, orang, gibbon, ape, rhesus);

myMonkey : monkey;

number :integer;

package monkey_io is new ada.text_io.enumeration_io(monkey);

begin

myMonkey := spider;

number := monkey'pos(Mymonkey);

ada.integer_text_io.put (number);

for i in monkey'first.. monkey'last loop

number := monkey'pos(i);

ada.integer_text_io.put (number);

end loop;

myMonkey := monkey'val(4);

monkey_io.put (myMonkey);

end testenum;

We also wrote factorial.adb shown in the block below and discussed why it needed to be a function not a procedure. Note that the code example has the erroneous attempt at writing it as a procedure present but commented out.

We deliberately tried entering an out of range value for N and verified that the error that would occur and need to be handled was a constraint error.

with ada.text_io;

with ada.integer_text_io;

procedure factorial is

num : natural;

--procedure FindFactorial(n : in out natural) is

function findFactorial (n : in natural) return natural is

begin

-- n! is n* (n-1)!

-- stopping case is n= 0

-- am I done?

if (n = 0 ) then

return 1;

-- return;

else

return n* findFactorial(n-1);

-- n := n * findFactorial(n-1);

end if;

end findFactorial;

begin

num := 5;

ada.integer_text_io.put (-5);

ada.text_io.new_line;

num := findFactorial(-5);

-- findFactorial (num);

ada.integer_text_io.put(num);

end factorial;