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
- pass-by-value
- pass-by-reference
- implicit type conversion for function arguments
- overloading function names
- recursion
- local variables and scope
- "the stack" of function calls
- 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.
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:
- 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
- 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!)
- Printing in binary
- Computing Continued Fractions
- Writing Continued Fractions in HTML
- Fibonacci Numbers
-
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:
-
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.
-
Take an uncovered coin from his stash and place it (same side up)
on an uncovered coin in the row.
-
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!