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: 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 doesn't care about how a function does something, he 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.

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.

The most important note you'll ever read: Programming nirvana - the most enlightened state of programming - is reached when you have perfectly achieved two goals:
  1. separation of interface from implementation, i.e. what is needed in order to use a thing is completely walled off from how the thing actually works, and
  2. code reuse, i.e. code you write for one project can be easily reused in all sorts of other projects, or reused within the same project (never duplicate code!).
These two goals are independent of what language you program in ... this is what everyone wants. In the paradigm (or style) of programming we cover in IC210, Procedural Programming, the primary language construct provided to support these two goals is ... functions! The prototype vs definition split, and the scoping rules for local variables within functions provide separation (perhaps imperfectly) of interface and implementation. Viewing programs as collections of functions provides code reuse, as well-designed functions from one project can be taken piecemeal and reused in other projects.

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);

// Return 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. Computing Continued Fractions
  3. Writing Continued Fractions in HTML
  4. Fibonacci Numbers
  5. Open-ended bottom-up design question
    Suppose I have the following game: Some number of coins are spread in a row across a table, in a random order, also with a random side facing up. Play commences in turns. For his turn, a player has three options:
    1. Take a coin (or two-coin pile, as we'll see later) from one of the two ends of the coin row, and add the coin(s) to his stash, keeping the same side(s) up. Note: piles stay piles in the stash.
    2. Take an uncovered coin from his stash and place it (same side up) on an uncovered coin in the row.
    3. Flip an uncovered coin (or the top coin in a two-coin pile) in the coin row — but this is only allowed if the player's previous move was not a flip!
    When the coin row is empty, each player sums up the values of the coins in their hands, counting heads-up coins as + their values, and tails-up coins as - their value. Whoever has the largest sum wins.

    Let's do bottom-up design. The fundamental object we have to deal with here are coin piles, which may consist of one or two coins. suppose we represent side value as heads-up = 0, tails-up a = 1, and coins by their denomination, i.e. 25 for quarters, 10 for dimes, 5 for nickles and 1 for pennies.
    one-coin piles: pilevalue = sidevalue + 10*coinvalue
    two-coin piles: pilevalue = sidevalueTop + 10*coinvalueTop + 1000*(sidevalueBottom + 10* coinvalueBottom)
    So, for example, if you have a quarter facing heads up, it would have pilevalue = 0 + 10*25 = 250. If you have a tails-up dime with a tails-up quarter on top, you would have pilevale = 1 + 10*10 + 1000*(1 + 10*25). we can unpack this stuff as follows (let pv be a pile value):
    if pv < 1000 then pv represents a 1-coin pile
    pv%10 is the sidevalue of the top coin
    (pv%100)/10 is the coinvalue of the top coin
    (pv/1000)%10 is the sidevalue of the bottom coin (if there is one)
    (pv/10000) is the coin value of the bottom coin (if there is one)
    	  
    Your job: use bottom-up design and start writing prototypes and definitions for the functions you'd probably want to have if you were ultimately going to implement this game!