CS 12 - Spring 2004 - Assignment 8

CS 12 - Assignment 8 - Recursion

Due via e-turnin by Sunday 5/30, 11pm

Collaboration Policy:
Collaboration on home programming assignments is strictly FORBIDDEN.
Programs must represent YOUR OWN original work.
Sharing code or team-coding are not allowed. Copying code from ANY source (any book, current or past students, past solutions, the web, etc.) is not allowed.
Cooperation to the extent of helping to debug, or discussing the general approach to solving the problem is encouraged, but should never involve communicating code or even pseudo-code or explicit algorithms. Your code must be unique.

Recursion is a powerful tool for solving programming problems, but one that requires a bit of practice and thought to understand how it works. In this assignment you will do a series of small recursive problems to help gain the practice needed to use recursion in your programming.

How to do it

The secret to recursion is really two things: trust and laziness. To write a function recursively, you usually only need to solve the simplest instance of the function (this is laziness.) This is called a "base case." Once you have a base case, assume that you have written the function correctly and let the function call itself to figure out the rest (this is trust.) This sounds really odd, so let us look at an example:

Lets say we want to find the maximum element of an array. What is the simplest case possible here? If the array has only one element in it, that element is obviously the maximum. If all arrays had only one element, this would be very simple indeed. We will use this as our base case.

int findMax(int array[], int size)
{
  if (size == 1) return array[0];
}

This works great if we only have arrays of size 1. How do we make this more general? We assume that we have the function working for "smaller problems", and write the rest in terms of calling itself. So, if we have a function findMax that works for smaller arrays, how do we write findMax to deal with arrays that are slightly larger? Lets think: the maximum of an array is the maximum of (the first element, and the maximum of the rest of the array). Lets look at that in code:

int findMax(int array[], int size)
{
  if (size == 1) return array[0];

  int result = findMax(array, size - 1);

  if (array[0] > result) 
    return array[0];
  else 
    return result;
}

Does this work? One line in here is not quite right:

  int result = findMax(array, size - 1);

This isn't really passing the "rest of the array" to the function, this is passing the same array and just claiming it is smaller. We'll always end up comparing the first element to itself!

Our base case is wrong, and it comes from a common mistake: if we are writing a recursive version of a simple iterative function, we often need to pass in an extra parameter. In this case, our parameter tells us where we are looking in the array, and each call to findMax returns the maximum value that occurs after that index.

int findMax(int array[], int size, int index)
{
  // This needs to be size - 1 because the array is 0-indexed.
  // This is our base case
  if (index == size - 1) return array[index];

  // Call the function recursively on less of the array
  int result = findMax(array, size, index + 1);

  // Return the max of (the first element we are examining, the max of the
  // rest of the array)
  if (array[index] > result) 
    return array[index];
  else
    return result;
}

The Specs

Write the following functions using recursion; where the exercise involves a data container, use a linked list (rather than an array, as above). There should be no loops in your solutions.

Recursion can also be used to do simple looping: write a function
```
void countTo(int start, int end)
```
that prints out all the values from start up to (but not including) end with an endl after each number. For example, calling countTo(4, 7) would produce
```
4 
5 
6 
```
Calculating integer logarithms: write a function
```
int intLog(int val, int base)
```
that returns the number of times you have to multiply base by itself to get something as large as val. (This only has to work for perfect powers like 64 and 2 or 9 and 3.)
Recursively find the node holding the minimum element of an linked list:
```
NodePtr findMinNode(const NodePtr& currentHead, const NodePtr& currentMin)
```
For example, if the list is {4, 3, 9, 2, 63, 1, 7} it would return a pointer to the 6th node, whose value is 1. In the case of ties, return the node first encountered.
Find the sum of the values in a linked list of integers.
Write a main function that creates a linked list of random integer values (you will need loops to do this, of course) and thouroughly tests all of your functions above.
Turn this in as "recursion.cc".