Lecture 19 – October 29, 2007

Lecture 18 was our exam – given October 24^th.

Do question 7 on the sheet handed out in class and turn it in on Wednesday.

If you have questions about your exam, please see me in my office.

Please do not write ON the exam.

A generic formal parameter can be an object; alternatively (unlike a parameter of a subprogram), it can be a type or a subprogram.

What to do about SORTING program??? You have until next Monday to “fix” it. The directions have been modified so you are now being asked to print each array after each pass (so that we can see the behavior more clearly). This program will be due next Monday, November 5^th with the electronic version due Sunday night the 4^th by 11:59 pm.

Josephus Problem

http://mathworld.wolfram.com/JosephusProblem.html

You are going to write a solution to the Josephus problem which will tell you the best place to stand (i.e. who will be the last person standing). The easiest way to do this is to use a circular queue. You can test your program with constant values but the final version should ask the user for: number of people in the circle; and the "count" that indicates who "dies". You should show the circle after each deletion and tell who was deleted. This program will also be due next Monday, November 5^th with the electronic version due Sunday night the 4^th by 11:59 pm.

Recursion – Chapter 9

Terms:

recursive call: A subprogram call in which the subprogram being called is the same as the one making the call.

direct recursion: recursion in which a subprogram directly calls itself.

indirect recursion: recursion in which a chain of two or more subprograms returns to the subprogram that originated the chain.

binding: the association of a memory address with a variable name.

binding time: the point in the compile/link/execute cycle when variable names are associated with addresses in memory. NOTE: binding time can also refer to the time when values are associated with variable names; as well as when types are associated with variable names, etc.

relative address: the offset (number of memory locations) from some other address determined at run time

activation record: a record used at run time to store information about a subprogram call, including the parameters, local variables, register values, and return address.

depth of recursion: the number of recursive calls used to complete an original call of a recursive subprogram.

tail recursion: the case where a recursive subprogram contains a single recursive call that is the last statement executed in the subprogram.

In Ada, any subprogram can call another subprogram.

Three Question Method

1. the base-case question: Is there a non-recursive way out of the procedure or function , and does the algorithm work correctly for this “base case”?
2. the smaller-caller question: Does each recursive call to the procedure or function involve a smaller case of the original problem? By smaller, we mean that it is closer to the base case. This guarantees that we ultimately reach the base case.
3. the general-case question: Assuming that the recursive call(s) work(s) correctly, does the whole procedure or function work correctly.

On the next page (i.e. below), you will find the program we did in class. Please determine what the program does and write it on the back of your solution to question 7 on the exam.

Ï

Ïwith ada.text_io;
ÏÏÏwith ada.integer_text_io;
ÏÏÏwith puzzle;
ÏÞßàprocedure testPuzzle2 is
ÏϧÏíÏbase, limit, result : integer;
Ïϧ
Ïϧ
ÏϧÏÞßàfunction puzzle (base : in natural;
ÏϧÏÏ§Ï limit : in natural) return integer is
ÏϧÏϧ
ÏϧÏϧÏíÏresult : integer;
ÏϧÏϧ
ÏϧÏϧbegin
ÏϧÏϨ¹³´if base > limit then
ÏϧÏϧÏ6¾¹¹Ïresult := -1;
ÏϧÏϧÏ÷´elsif base = limit then
ÏϧÏϧÏ6¾¹¹Ïresult := 1;
ÏϧÏϧÏö´else
ÏϧÏϧϸ¾¹¹Ïresult := base * puzzle (base + 1, limit);
ÏϧÏϧϸÏ
ÏϧÏϧÏÈÏend if;
Ïϧ¹Ĺ¹Ïreturn result;
ÏϧÏϧ
ÏϧÏϧÏðîìexception
ÏϧÏϧÏϨ¹³´when constraint_error =>
ÏϧÏϧÏϧÏ6¨¹¹Ïada.text_io.put_line
ÏϧÏϧÏϧÏ6§ÏÏÏÏ(" oops, I forgot to tell you to give me a natural number ");
Ïϧ¹ÄÏϩ϶¾¹¹Ïreturn 0;
ÏϧÏÏ©end puzzle;
Ïϧ
Ïϧbegin
ÏϨ¹¹±for i in 1..5 loop
ÏϧÏÏ7¹¹Ïada.text_io.put (" please enter an integer ");
ÏϧÏÏ7¹¹Ïada.integer_text_io.get (base);
ÏϧÏÏ7¹¹Ïada.text_io.new_line;
ÏϧÏÏ7¹¹Ïada.text_io.put (" please enter an integer ");
ÏϧÏÏ7¹¹Ïada.integer_text_io.get (limit);
ÏϧÏÏ7¹¹Ïada.text_io.new_line;
ÏϧÏÏ7¹¹Ïada.text_io.put (" for the integers: ");
ÏϧÏÏ7¹¹Ïada.integer_text_io.put (base);
ÏϧÏÏ7¹¹Ïada.text_io.put (" and: ");
ÏϧÏÏ7¹¹Ïada.integer_text_io.put (limit);
ÏϧÏÏ7¹¹Ïada.text_io.put (" the result is: ");
ÏϧÏÏ7¹¹Ïresult := puzzle (base, limit);
ÏϧÏÏ7¹¹Ïada.integer_text_io.put (result);
ÏϧÏÏ7¹¹Ïada.text_io.new_line;
ÏϧÏÏ°end loop;
ÏÏ©end testPuzzle2;