Testing, Testing, 1, 2, 3, 4, 5 . . .

In this lab we would like to solidify two concepts: code testing and recursion. You will need a partner for this lab, preferably someone that you do not usually talk to.

Testing

Thorough and rigorous testing is a required step when writing good code (the opposite of unmaintainable code). The question is, of course, "How do I test my code?"

There are a few things to remember when testing code: So remember to do AT LEAST the following:

Testing Tools

Two tools that will help you immensely are diff and gdb. Diff you have probably run into already during this course. It simply takes two files and compares them. If they are not the same it prints out what changes would have to be made to make one into the other. For those of you familiar with Unix Pipes, diff works great with stdin. We have covered diff a few times already. Anyone that is not familiar with it yet should check the man page for diff.

Another wonderful tool for testing is gdb, the most common debugger for Linux. (Hopefully you remember using a debugger in CS 10. gdb gives you most of the power of the debugger in MSVC, and a lot of other good features.) We will cover the use of gdb next week, but if you have some time you may want to start investigating how to work it.

Recursion

Recursion is a powerful programming technique where you let a function solve some problem by calling itself so 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(5) would return 8 (if we behave like computer scientists and start counting with 0). 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(n)
{
    // If it is one that we know to start with, 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:
Find a partner. WITHOUT COLLABORATING, each of you should write up a solution to the following problem:

Write a program using recursion that calculates the factorial function (!). (Remember that n! = n * (n-1) * (n-2) * ... 1.) On startup it should print "Factorial Solver". It should then loop until EOF, prompting the user for input with the prompt "n (1-10): ", and then calculate the factorial of n, and print out the result.

When you and your partner are both done, show the TA. Once they give you permission, swap programs (use Pine to email each other your code as an attachment), and see if you can find a way to break the other person's program. Use the following sample input and output files and diff to see if they followed the directions rigorously.

When you are done, explain your findings to your partner. Turn in a directory containing your code as "lab4.cc", theirs as "partner.cc", and a text file containing what you tested, and any comments you have about their code (style and functionality comments are OK.) Your comments should be "comments.txt".

.2 points:
Edit "comments.txt": does your partner's code meet the course style guidelines?

.2 points:
Add to "comments.txt": Describe a method for using the sample input and output files and diff to test your partner's program. You may want to look at the assignment pages for this quarter so far.

.2 points:
What is the largest integer n such that n! fits in a signed integer? Is this larger or smaller than you expected?

.2 points:
Add the following line to the beginning of your code. Save it, close it, and reopen it under Emacs. Re-indent everything. What does this do? 
/* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 3 -*- */


.2 points:
Write a program that uses a recursive function to compute integer powers. It should take in two inputs, x and n, and return x^n. Submit this program as "power.cc".

.2 points:
The recursive solution to the Fibonacci problem that we presented in this lab is very inefficient. Why? (HINT: Write out the functions that have to be called to solve fib(5))

.2 points:
Using gdb, set a breakpoint in the first line of the recursive solution to the Fibonacci function. How many times does gdb think the function is called in fib(5)?

.2 points:
What options do you have to add to your .emacs file to set the tab width to 3 characters?