SI204 Class 21: Looking Back at Functions


More Recursion

The "Problems" section below contains several more recursion problems, problems which are a little more sophisticated.

What we've learned about functions

The ideas behind functions in programming are very important, and we've covered a lot of ground in the past few weeks. For example:

         prototype versus definition

         return type and arguments/parameters



         implicit type conversion for function arguments

         overloading function names


         local variables and scope

         "the stack" of function calls

         using the debugger with functions

         Top-down design

When looking at this list of topics remember this: the most important thing to understand about functions in how they help us solve programming problems. A function can be viewed from the perspective of a user or from the perspective of an implementer. The user usually doesn't care about how a function does something, he or she just cares about what the function does. For example, you (and I) have no idea how the cos function from cmath works, but we do know what it does (give it a double r and it returns a double representing the cosine of r), and that's enough to use it correctly.

Essentially, the prototype (along with a comment or two) is all that the user of a function needs to know. The definition of the function is the realm of the implementer, who, of course, has to figure out how the function is going to do what it's supposed to.

When you work in groups, one person simply uses a certain set of functions in his part of the code, and the other person implements those functions. It's a convenient way to divide up work, because once we agree on what the functions are supposed to do (i.e. figure out prototypes, etc) we can go our separate ways and work on our own.

Within a program you write by yourself, functions are equally helpful, because they allow you to break up a large program into pieces that you can solve separately. Thus, no one piece is a big deal. In such cases, you are both user and implementer at different times - but never both at once! In top-down design, you are a user first, as you write a program assuming the existence of a "wish-list" of functions. Then you go ahead and implement each of these functions separately - and separate from the larger program. If you did things the other way 'round, it would be bottom-up design.

Bottom-Up Design

In bottom-up design you are the implementer of little functions first, and later you get around to using them in a larger program. For example, suppose you knew you were going to have to write a program that did some calculations with vectors for some basic physics problems. It's clear that you'll probably want to read, write, and add vectors, and probably you'll want to do dot products and get the length of vectors. Putting all this together, and remembering that a vector will consist of two double values, we get the following prototypes:

// Read vector from stream IN and return through reference variables x and y
void read(double& x, double& y, istream&IN);
// Write the vector (x,y) to stream OUT
void write(double x, double y, ostream& OUT);
// Add vectors (x1,y1) and (x2,y2) and return through reference variables x and y
void add(double x1, double y1, double x1, double y2, double& x, double& y);
// Return the dot product of (x1,y1) and (x2,y2)
double dot(double x1, double y1, double x1, double y2);
// Retrun the length of (x,y)
double length(double x, double y);

Whatever it is that I ultimately do in my program, if I have these functions I'll probably be OK with the vector part. So I'll go ahead and implement these now, and worry about the larger program later. That's what bottom-up design is about.


Problems (More recursion Practice!)

1.      Printing in binary

2.      Number of characters to print a number

3.      Computing Continued Fractions

4.      Writing Continued Fractions in HTML

5.      Fibanocci Numbers

Assoc Prof Christopher Brown

Last modified by LT M. Johnson 10/10/2007 01:16:00 PM