Before you start writing any code, in any computer program, you need to know exactly how your code will work. It is no good just copying random code and trying to tie it together somehow; you have to

What makes this hard is that usually you are trying to go from a

My uncle works at a company that does a lot of programming, and he says that when he interviews a condidate for a job, he can tell almost instantly whether they are a good programmer or not by how they approach a sample problem. Some people will immediately start writing down code that feels plausible, and then will see what it does, and if it doesn't work, fuss with it until it actually does what it is supposed to. Others will sit for a while and analyze the problem carefully, then write teh code correctly the first time. I'm sure you can figure out for yourself who ends up getting the job.

- First, think out what sort of "count" you will be keeping. Are you counting up, or down? Counting by ones, or doing something more interesting? The
`for`

loop is a great friend to you here, because it puts all this information together in one place. - Are there any values other than the count that you need to keep track of between loops? These variables should be declared before the loop starts.
- What exactly happens in each time through the loop? Be careful that it will set up properly for the next time through the loop.

- A pythgorean triple is a set of integers (a, b, c) for which a < b < c and a² + b² = c². Print all pythagorean triples for which c is less than or equal to 20, and count how many there are.

I think to myself:

- I am searching for values for these three variables. I know that
`c`

has to be an integer, less than or equal to 20. This means that`b`

can be at most 19, and`a`

can be at most 18. A good place to start is to loop through all possible values of`a`

:

for(int a = 1; a <= 18; a++) { - As I do this, I need to count how many triples I find. So, I should declare a variable -
`int count`

- outside the loop to keep track of this. - Next, I think about what I will do with each value of
`a`

. I say to myself,*"For each value of*Notice how I have turned my description into a procedure: I am now doing a`a`

, I want to find every value of`b`

for which a² + b² is a square number."**search**through possible values of`b`

in order to find one that meets some condition.

The phrase "every value of`b`

" in my little description above suggests that there is another loop going on inside the one I already have. Again, the first step is thinking out how the counting will work. I know that`b`

has to be greater than`a`

; that makes (`a`

+ 1) a good starting point. But what is the maximum value of`b`

? Looking back at the problem, I know that √(a² + b²) has to be less than or equal to 20. So:

for(int b = a + 1; Math.sqrt(a * a + b * b) <= 20; b++) { - Now I have to think to myself what will happen inside this inner loop. First I take a second to take stock of what I know about my variables each time through:
- I have two integers,
`a`

and`b`

- They define a right triangle whose hypotenuse is less than or equal to 20
`b`

is greater than`a`

- I want to know if their hypotenuse is an integer.

`c`

as a`double`

. It looks like this:

double c = Math.sqrt(a * a + b * b);

The trick is to figure out whether this is an integer. Digging into my bag of tricks, I remember that I can round off a double to an int by adding .5 and then truncating to an integer. So, perhaps I should round the square root to an integer, and then check if the equivalence is still true:

int c = (int)(Math.sqrt(a * a + b * b) + .5);

if(c * c == a * a + b * b) {

System.out.println("(" + a + ", " + b + ", " + c + ")");

count++;

} - I have two integers,

public int triples() {

int count = 0;

for(int a = 1; a <= 18; a++) {

for(int b = a + 1; Math.sqrt(a * a + b * b) <= 20; b++) {

int c = (int)(Math.sqrt(a * a + b * b) + .5);

if(c * c == a * a + b * b) {

System.out.println("(" + a + ", " + b + ", " + c + ")");

count++;

}

}

}

return count;

}

In general, looping problems will clearly have either a process that is repeated over and over again, or a range of numbers that you need to search through. Later on in the course, we will also see situations where you are looping through a

`String`

, as many of you did with Lindenmeyer systems, or where you are looping through a collection of objects.So, the process of figuring out a recursive solution to a problem looks like this:

**First**, you have to describe exactly what it is that your method accomplishes - it moves a stack of`n`

disks to a different tower, or it multiplies two numbers. Part of your task here is to write the signature of the method - think carefully about what information needs to go into it, and what it will give back.- Next, think out how you can reduce one particular case into one or more simpler cases, and then combine the answers. So, for example, you say, "Moving n disks means moving n-1 to the extra tower, then moving the nth disk, then moving the n-1 back on top of it." You can go ahead and write in this code, which is usually very simple.
- At this point, you have a method that will run forever. You need to identify a
**base case**, some point that the program will always reach, when it gets to sufficient depth, and that can be answered with a simple answer rather than a more complex one. The base case will be identified with an`if`

statement.

As an example, suppose that I have a method

`double f(double x)`

that represents some mathematical function. Here is an example of an `f`

that is a simple cubic funcion:

double f(double x) {

return .5 * x * x * x + 1 * x * x - 2 * x - 3;

}

A plot of this function - draw, appropriately enough, by a

`Turtle`

- is shown to the right. As you can see, I have labeled the `x`

and `y`

intercepts of the function.Suppose that you wanted to write a method to locate one of the roots of this function - that is, an

`x`

value for which `f(x)`

is 0. You would have to specify what range of `x`

's to look in, since as you can see there are three roots. So, my method might look something like this:

// Return the x value in the given range for which f(x) = 0

public double root(double minX, double maxX)

So, for example,

`root(0, 4)`

ought to return 1.865, and `root(-2, 0)`

ought to return -1.2111.If I want to implement this method recursively, I think to myself: "How can I simplify the task of looking for a root in the given range?" Well, a simple way to do it would be to narrow the range. I will do this by figuring out where the function changes sign - in the first half, or the second half. Wherever that happens, I can call

`root()`

again with a reduced range just containing half of the original range:

// Return the x value in the given range for which f(x) = 0

public double root(double minX, double maxX) {

double midX = (minX + maxX) / 2;

if(f(maxX) * f(midX) < 0) {

// If multiplying these two gives a negative number, they are opposite in sign.

// So, the function crosses the axis in the first half

return root(minX, midX);

} else {

// Otherwise, the function crosses the axis in the second half

return root(midX, maxX);

}

}

As usual, I find myself with a method that really ought to work, except that it will never terminate: it just keeps looking at smaller and smaller ranges. I need to introduce a "base case" that will end the whole process when we get to a difference that is too small to matter. A simple way to define this would be to stop when the width of my range is too small to be noticeable; if it is, say, less than .00001, then the error must be less than that.

// Return the x value in the given range for which f(x) = 0

public double root(double minX, double maxX) {

double midX = (minX + maxX) / 2;

if(maxX - minX < .00001) {

return midX;

} else if(f(maxX) * f(midX) < 0) {

// If multiplying these two gives a negative number, they are opposite in sign.

// So, the function crosses the axis in the first half

return root(minX, midX);

} else {

// Otherwise, the function crosses the axis in the second half

return root(midX, maxX);

}

}

`sandwich()`

`n`

to be a `String`

containing the number `n`

enclosed between two sandwiches of size `n - 1`

. A sandwich of size 0 is an empty string. So, for example, `sandwich(2)`

= "121", and thus `sandwich(3)`

= "1213121".Write both a recursive and an interative method to calculate this. Be sure that you carefully work out how each method works before you start writing code.

What would you modify if you wanted each sandwich to be enclosed in parentheses, as in "(((1)2(1))3((1)2(1)))"?

What would you modify to take the nubmers out of the above pattern, so that

`sandwich(3)`

just returns "((()())(()()))"?Solution to sandwich()

(Lessons) (Previous: Lesson: Fractals) (Next: Lesson: Recursion Review)