Introduction to Recursion

This is a brief outline of the lecture.

Defn: A method m(...) is said to be recursive if m(...) calls itself (i.e., the same method, with the same number and type of parameters). The recursive call could be made directly within m(...) or indirectly through several other method calls.

We wish to practice writing recursive methods.

Prerequisite: Understand the runtime stack.

To write a recursive method for some task, ask yourself three questions:

1. What slightly simpler problem can I ask a friend to solve whose answer would make my problem easy?
2. What simple cases can I do myself?
3. How can my friend and I communicate the problem and partial solution?

Example 1 On the board in class we designed, wrote, traced, and debugged a recursive method to remove the first occurrence of an object o from a stack s, leaving the other items in the stack in FIFO order.

Solution. Answers to 3 questions:

1. Let us deal with the top item on the stack (if any), and ask a friend to help with the rest of the stack. Our friend gets a shorter stack, therefore it is a simpler problem.
2. If the stack has size 0 or 1, we could deal with it. (Let's just deal with size 0.) If the top item is o, and we haven't removed o yet, then lets remove it ourselves.
3. boolean deleteFirst(Stack s, Object o) -- the stack referenced by s will get shorter and shorter as more friends are called. However, the reference to the stack will not change.

/** Remove the first occurrence of o from the stack s.
 *  @param s the stack, must not be null.
 *  @param o the item to be removed, must not be null.
 *  @return true if the item was found and removed, else false. */
public static boolean deleteFirst(Stack s, Object o) {
  if (s.size() == 0)
    return false;
  Object current = s.pop();
  if (o.equals(current))
    return true; // toss current
  boolean result = deleteFirst(s, o);
  s.push(current);
  return result;
}

Key Point In writing this code it is easiest if you trust your friend to do their job. Don't think about how your friend does their job (this often gets messy). Just make sure you do your job.

Example 2 Given a non-null Queue q, reverse it.

Solution. Answers to 3 questions:

1. Let us deal with the first item on the queue (if any), and ask a friend to help with the rest of the queue. Our friend gets a shorter queue, therefore it is a simpler problem.
2. If the queue has size 0 or 1, we could deal with it.
3. public static void reverse(Queue q)

Exercises

1. Do a detailed trace, using the Java memory model, of deleteFirst(s,o) where the stack s contains String items "a", "b", "c", "d", "e", and o is the String "c". Where do all the items referred to by current get stored in in the runtime stack?
   
   
2. Write and check the code for example 2.