Learn Programming in Java


<<Previous | ToC | Next >>

Lesson #5: Subroutines & Recursion

One important characteristic of good programming style is the appropriate re-use of code. Programs can -- and will -- get very big very quickly, but small programs are easier to manage and get working properly. You already saw this characteristic at work when we replaced three separate (but nearly identical) snippets of code to ask the next question in the guessing game with code to ask the same question inside a for-loop executed three or more times.

Later we built nested for-loops to draw the Tic-Tac-Toe board. The squares we drew were not identical, so we had to add some if/else conditions to accommodate the differences. The essential programming skill that you must develop to be good at this, that is to recognize when two pieces of code are similar enough to justify making a single block of code serve both needs, and when that is impractical because the differences are too great. There is no single rule to help you decide that, you basically write both versions (in your mind, if not actual code) and look for similarities, and then weigh the costs against the benefits. Every line of code (except comments and uninitialized declarations) takes time to run and uses up space in memory. If you must add too many qualifying if/else lines to enable sharing, then the merged code might be too slow or too big (or both) to justify it. One of the things good compilers do to make code faster is unroll loops (convert them back to linear code) to eliminate the loop overhead. You don't need to worry about this until your program becomes unacceptably slow. That won't happen any time soon.

Today you will learn about another powerful mechanism for sharing code -- the technical term is code re-use -- which is subroutines. It is more powerful than loops because you can re-use the same code in widely distant parts of your program. Consider again that TTT program, there are four different places where we examine all eight ways (three rows, three columns, and two diagonals) to win at the game, and another eight places that do the same test on a single row, column, or diagonal. The four are almost identical -- deciding that X won, deciding that O won, and also deciding that playing an empty square would prevent X from winning or enable O to win -- differing only in which variable is being considered (eX, which is all of the squares played by X, Oh, the same for O, or else test representing the combination of played squares and the empty square being considered).

A subroutine -- in Java it's called a "method" for no particularly good reason -- consists of a header which specifies the type of result it calculates and returns (if any), and gives a name both to the subroutine itself and also names and types of all the values it should work with, called parameters, and one or more places in the method code where the returned result is defined (if so; it is also possible for a subroutine to do something that has no result that the caller cares about. Subroutines that return a value are usually called functions because that's what they were called in mathematics, and "subroutines" otherwise, but "method" refers to either kind without distinction. The subroutines we did in Chomp had neither defined parameters nor a returned value. Here for example is a "Winner" method to decide if there is a winning row, column, or diagonal in the play list being considered:

  public static boolean Winner(int playlist) { // <-- header, one parameter
    if ((playlist&0xE)==0xE) return true; // top row wins
    if ((playlist&0x70)==0x70) return true; // middle row
    if ((playlist&0x380)==0x380) return true; // bottom row
    if ((playlist&0x92)==0x92) return true; // left column
    if ((playlist&0x124)==0x124) return true; // middle col
    if ((playlist&0x248)==0x248) return true; // right column
    if ((playlist&0x222)==0x222) return true; // down diagonal
    if ((playlist&0xA8)==0xA8) return true; // up diagonal
    return false; // there is no winning three
  } // end of Winner


Unlike conditionals and loops, the outer braces are always required, and if a result is to be defined -- in this case the result is a boolean value, true if there is a winning row or column in the playlist, and false otherwise -- there must be a "return" statement giving that value in every possible execution path before the ending brace. Inside the parentheses of the header is a comma-delimited list of what looks -- and acts -- like variable declarations called parameters. Each parameter is effectively initialized when the function is called, which is where it replaces code, like this, where:

// did O win?
if (Winner(Oh)) Owon = true;
replaces these nine lines:
// did O win?
if ((Oh&0xE)==0xE) Owon = true; // top row
else if ((Oh&0x70)==0x70) Owon = true; // middle row
else if ((Oh&0x380)==0x380) Owon = true; // bottom row
else if ((Oh&0x92)==0x92) Owon = true; // left column
else if ((Oh&0x124)==0x124) Owon = true; // middle col
else if ((Oh&0x248)==0x248) Owon = true; // right col
else if ((Oh&0x222)==0x222) Owon = true; // down (1-5-9) diagonal
else if ((Oh&0xA8)==0xA8) Owon = true; // up (7-5-3) diagonal
and:
if (Winner(eX)) Xwon = true;
replaces:
if ((eX&0xE)==0xE) Xwon = true; // top row wins
else if ((eX&0x70)==0x70) Xwon = true; // middle row
else if ((eX&0x380)==0x380) Xwon = true; // bottom row
else if ((eX&0x92)==0x92) Xwon = true; // left column
else if ((eX&0x124)==0x124) Xwon = true; // middle col
else if ((eX&0x248)==0x248) Xwon = true; // right column
else if ((eX&0x222)==0x222) Xwon = true; // down diagonal
else if ((eX&0xA8)==0xA8) Xwon = true; // up diagonal
Similarly, we get:
test = Oh|aBit; // try for a win..
if (Winner(test)) score = 99;
or even better, replacing all nine original lines with:
if (Winner(Oh|aBit)) score = 99; // yay! (a winner)
and then also:
if (Winner(eX|aBit)) score = score+22; // prevent a lose, block this one


Notice that in these last two cases we no longer need to use a temporary variable (test) to build the hypothetical play in this empty square to see it it wins or loses, because the parameter takes the place of that temporary variable.

Because every name used in Java must be declared before it is used, we put the new Winner method code before the main() declaration. In case you didn't notice, main() itself is a method. The name main is magical, and gets called by the system to run your program.

We are not done yet. There are those eight other places where we do similar things with the whole board, by rows and columns; can we use the same method to replace all that code too? Think with me for a minute or three about that non-loop in the part of the program that decides where to play O... For each of the eight possible wins, we set up the mask variable, then repeat these same four lines to decide how much to add to the score:

if ((mask&aBit) !=0) if (((both|aBit)&mask) != mask) {
  if ((both&mask)==0) score++; // row is empty
  else if ((Oh&mask)==0) score = score+2;
  else if ((eX&mask)==0) score = score+4;}
depending on if that row or column or whatever is blocked by already having both an X and and O in it. We need to test each row or column separately, because a row might be blocked but not the diagonal (and so on), and if so, then you can still win or lose on that square. So while our Winner method returns true if there is any winning row or column for the play being considered -- that is, at least one winning direction, and ignore any others -- to decide if a play cannot win needs to test them all. There may be a way to merge this functionality into the Winner method, but I don't see it. But the four lines are identical, so they are a candidate for their own method, call it Add2score, and it needs to know five numbers, which we will give the same names as parameters:
public static int Add2score(int eX, int Oh, int both, int aBit, int mask) {
  if ((mask&aBit) ==0) return 0; // the current square is not in this row
  if (((both|aBit)&mask) == mask) return 0; // this row has both X and O
  if ((both&mask)==0) return 1; // the row is empty
  if ((Oh&mask)==0) return 2; // it has one X only
  if ((eX&mask)==0) return 4; // it has one O only
  return 0; // probably can't get here, but the compiler requires a return
} // end of Add2score


Where each instance of those five lines now becomes something like:

score = Add2score(eX,Oh,both,aBit,0xE)+score; // top row


I leave the other seven instances for you to fill out. See if you can make these new methods work yourself, before looking at my code. When you get a clean compile and go to run it, you now have the two new methods listed in the popup. I guess that's so you can test them separately (called unit testing) before integrating the whole thing into a run. Usually I just start from the top (choose main) each time, but if you are responsible for your method and the rest of the team is not ready to call it, unit testing is the way to go. Anyway, in the Debugger, use the "Step Into" button to step into the subroutine instead of running through it all in one click.

I mentioned that the main() we have been using all this week is just another subroutine like Add2score and Winner, but there are a couple of differences. Obviously the number of parameters is different (none instead of one or five), but one word I have not yet explained to you is the subroutine return type "void" which means there is no result to be returned. Perhaps you noticed that there is no "return" statement in the main() we have been working with, but if we decided to return early, it would be just the word "return;" with no value. In a strongly typed language (which Java tries to be, but does not entirely succeed) "void" would be just another data type, the natural type of statements, so a call to a void subroutine is just another statement -- and so it is! Except Java also lets you implicitly discard the result of a function by calling it on a statement line. Because main() is type "void" it can only be called from a statement.
 

Recursion

One of the most powerful ways to use subroutines is called recursion, where the subroutine (method) calls itself. If the subroutine only calls itself at the end (tail recursion) it is equivalent to iteration, that is, you can do exactly the same thing using either a recursive subroutine calling itself, or with a while or for-loop, and except for the loop or method overhead, all the rest of the code would be essentially the same. But it's not important for you to know that unless you are trying to convert a Java program to Lisp or some language like that -- Lisp has no explicit iteration, to do loops you must use recursion, but you can think of it as just a different way to spell "while".

Much more useful is the ability of the subroutine to call itself in the middle, before it has reason to return. Next week we will look at recursive data structures, which require this kind of access, but lead to awesome computational capabilities.

For now we will introduce recursion with a common mathematical function called factorial. You may have seen this in math class: the factorial of 0 is defined to be 1, and the factorial of any larger (integer) number is that number times the factorial of the next number down. Thus the factorial of 1 is 1 times the factorial of 1-1=0, which is defined as 1. Factorial(2) is 2*factorial(1), =2, and so on. In Java it would look like this:

int Factorial(int whom) {
  if (whom==0) return 1;
  return Factorial(whom-1)*whom;
} // end of Factorial


Because this is tail-recursion, we can do the same thing with a for-loop, where whom is the (same) starting number, and fact is the result:

int fact = 1, whom = 7; // give whom a starting value
for (whom=whom; whom>0; whom--) fact = fact*whom;


Or you can leave off the superfluous "whom=whom" assignment in the for-loop header, but I wouldn't recommend it; it's better to show people (who might be reading your program, including yourself next week or next month) what your intentions are:

for (; whom>0; whom--) fact = fact*whom; // (works the same, but not best form)
 

Abstraction

One of the important things that subroutines do for us is called abstraction. This is subtle, but extremely useful. When you click on the Compile button in BlueJ, a lot of things happen, but you don't need to think about all those things. In the Bad Olde Dayes of computing, when command lines ruled the world, what you now do with a single click, back then required a dozen lines of job control language, individual command lines to do one step at a time. Each programmer had to do all those steps every time. That's a lot of cognitive effort that you don't need to expend, because somebody else encapsulated all that into a single button click. You can think "Compile" and click a single button that says "Compile," and all those details are hidden from you. You can use your mind for looking at the girls across the room, or (more usefully) for thinking about what you want to do next.

Everybody has the same number of brain cells (unless you fry them with drugs), and if you focus your brain cells on how to program the Big Picture problems instead of continually re-thinking the piddly details, you will be a super-programmer instead of a piddly coder. Somebody must write the low-level details. You will need to write the low-level code, but encapsulate it, put it into a subroutine with appropriate parameters, and never look at it again -- unless it's broken and you need to fix it or add a feature, but wrap it back up and stop looking at it. Write a block comment at the front to remind you (and everybody else) how to use it. If you keep needing to look inside to use it, you bungled the encapsulation, and you should rethink the problem so you don't need to look. But don't feel bad, it happens to all of us! Fix it and move on.

In the next lesson we will look at a mechanism that enforces the abstraction and information hiding you already can do with subroutines.

Next: Classes & Objects

<<Previous | ToC | Next >>

Revised: 2020 February 27