CS 12 - Fall 2003

CS 12 - Recursion

Recursion

Recursion is a powerful programming technique where you let a function solve some problem by calling itself to solve a slightly-easier version of the same problem. Let's look at an example:

Suppose we want to write a function to calculate Fibonacci numbers (the Fibonacci sequence is: 1, 1, 2, 3, 5, 8, 13, 21, 34 . . ., where each number is calculated as the sum of the previous two numbers, and the first two numbers are ones (1)).

int fib(int n)

We take in a number n, representing which Fibonacci number we want to calculate, and return the value of that number. Thus fib(6) would return 8. Let's look at two ways of writing this function:

// The iterative version
int fib(int n)
{
    // Figure out the first two numbers
    int fib1 = 1;
    int fib2 = 1;

    // If they asked for either of the first two numbers, 
    // we already know what the answer should be. 
    if (n <= 1) return 1;
    
    // Otherwise, calculate
    for (int i = 1; i < n; i++)
    {
        // Figure out the new number
        int newNum = fib1 + fib2;

	// Update
	fib1 = fib2;
	fib2 = newNum;
    }

    // Return the answer
    return fib2;
}

Using the iterative approach, this is not too bad. There are a couple of tricky bits here, like figuring to use a new variable when calculating each new number in the series, and just how to do the calculation, but overall it isn't too bad. Let us take a look at the recursive solution.

// The recursive version
int fib(int n)
{
    // If it is less than 2 then we know the initial case, return it
    if (n <= 1) return 1;

    // Otherwise, calculate the previous two and return the sum
    return fib(n - 1) + fib(n - 2);
}

Admittedly, the recursive version is a little harder for some people to understand. Still, it is a much more concise version that more closely mimics the mathematical definition. Pretty neat, eh?

The Assignment

7 points:
Write a program that prompts the user to enter up to 20 integers (use Ctrl+D to indicate premature termination). Once done, your program should print out the minimum and maximum values, and also the number of elements divisible by 3, each calculated by its own recursive function (the headers for each are provided below):

int min(int array[], unsigned int length, int pos)
int max(int array[], unsigned int length, int pos)
int divByThree(int array[], unsigned int length, int pos)

0.5 points:
At some point Fibonacci will return a negative value, which is incorrect since Fibonacci always should return a postive value. Explain why the Fibonacci function will return the negative value and how can you correct this.

0.5 points:
Write a program that recursively calculates the factorial function (!). (Remember that n! = n * (n-1) * (n-2) * ... 1.)

If you finish early, you should work on assignments.