None.

## More Recursion

The "Problems" section below contains several more recusion 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
• pass-by-value
• pass-by-reference
• implicit type conversion for function arguments
• recursion
• 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 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.

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 refernce 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 refernce 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
6. 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 dsign. 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 denomiantion, 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!