1
h05
CS32 F18
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h05: Recursive Algorithms

ready? assigned due points
true Tue 10/16 08:00AM Tue 10/23 02:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the four lowest scores (if you have zeros, those are the four lowest scores).

Reading: Recursive Algorithms, DS 9.1, PS 14.1 and 14.2

  1. (10 pts) Fill in the information in the header. The following are required to get the 10 "participation" points.
    • Filling in your name and umail address.

    Also: For paper submission PLEASE submit on ONE SHEET OF PAPER, double-sided if at all possible. If you must submit on two printed sheets write name on BOTH sheets and no staples, paperclips, or folded corners.

  2. Activation records are stored on the "run-time stack".
    1. (4 pts) Why is a "stack" an appropriate data structure for the storage of activation records?
    2. (4 pts) What event is associated with the push() operation onto the run-time stack?
    3. (4 pts) What event is associated with the pop() operation from the run-time stack?
  3. List two important pieces of information stored in an activation record:
    1. (4 pts) 1.
    2. (4 pts) 2.
  4. There are two important parts to every simple recursive function: the base case, and the recursive call that makes progress towards the base case. (There are other forms of recursion, such as "mutual recursion", where foo() calls bar() and bar() calls foo(), but let's set those aside for the moment, and deal only with simple recursive functions). Something that can go wrong with recursion when it is used incorrectly is a stack overflow. Explain two different ways that a recursive function could be writen incorrectly that could leave to stack overflow. Hint: one has something to do with the base case, and the other has to do with the recursive call.
    1. (5 pts) 1.
    2. (5 pts) 2.
  5. (10 pts) Given a fairly common definition for a struct Node that can be used to make a linked list of int values, along with a conventional implementation of a function that prints the value of the linked list, one per line. Rewrite the function as a recursive function. Hint: the base case is an empty list — in that case, do nothing (just return). Recursive call should print the first element on the list, then recurse on the "rest" of the list. 
    6. struct Node {
  int data;
  Node *next;
}

void printList(Node *head) {
   for (Node *p=head; p!=NULL; p=p->next) {
      cout << p->data << endl;
   } 
}