CS 12 - Fall 2003 - Assignment 2

CS 12 - Recursion

Recursion

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. There should be no loops anywhere in your code.

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 index of the minimum element of an array: int findMinIndex(int array[], int size, int pos). For example, if the array is [4, 3, 9, 2, 63, 1, 7] it would return 5, the index of value 1. In the case of ties, use the smaller index.
Find the minimum element of an array.
Find the sum of the values in an array of integers.
Find the number of odd integers in an array of integers.
Find the number of integers in an array that are divisible by a given value. (int findDivis(int array[], int size, int pos, int divisor)).
Write a main function that thouroughly tests all of your functions above.
Turn this in as "recursion.cc".

Bonus credit: For up to 5 extra points, read the section in the text about the vector type and re-implement all of the above functions that use arrays to use vectors instead. Do not pass in a size value.