![]() ![]() 16 June 2000
|
![]() |
Welcome back to the continued lesson on recursion, a way of doing
call-backs from a method to the method itself. We will also add a touch on the Java graphic package and will use
recursive calls while painting. |
||||
Extended recursion
Mainly, recursion is used when several tasks have to be done at the
same time. Of course a computer (at least a single CPU machine) only handles one task at a time, but abstractly
speaking, several tasks are done in parallel. Several examples are used to illustrate the idea and a lot of impressing
sorting algorithms are built on recursion (but sorting will not be dealt with in these columns unless quite a
few makes requests for that). We will use a quite nice graphical example instead, that literally will show us
how this works. |
|
The image to the right shows what happens if you erase the last line
of the
drawRuler
method.
The middle ruler is drawn, the second highest ruler and down to the lowest one every ruler to the left is drawn.
But no one ruler to the right, obviously since the last line of the code is erased. But this gives us a clue of
what is happening inside the computer, too.
Even if the last line of the method is there the first eight rulers
drawn will look like the image to the right. Since each recall to drawRuler
takes us more and more to the left until the expected level is reached,
no call is ever made to a right ruler. The first time we ever enter the last line of the method is when the leftmost
ruler is completed and drawRuler
returns
at the trivial case. Then we draw a ruler to the right, but still the level will be at the lowest possible so
no more rulers will be drawn.
The method returns up the second lowest level possible only to
find that the last line is still not done so it now dives to the right. Only to have to go the left. Yes, I see
this is not easily explained <grin>. I will then use a white board sketch.
Here are less rulers and they are numbered from one and upwards
as they are drawn. It is easily seen that we are going leftward until we reach the bottom level, there we try
to go one step further but find the trivial case and is returned to number 4. In number 4 we try to go to the
right, but again find the trivial case and end up at 4 again, with nothing more to do. Hence we return to the
method that called number 4, that is number 3.
In number 3 there are one line undone, the last one that sends
us to the right, which will be number 5. In number 5 we draw another ruler and then try to go to the left--the
trivial case is found--and we try the right side--again the trivial case--so we return upwards to number 3. There
we find that we are done with number 3, so we return to number 2, which will send us down to number 6, that draws
that ruler and then turns to left, the "left" code line. This way we swirl around until we finally reach
number 15 and wind ourselves up to number 1 and find that now we are done with this recursive lesson. Thirtyone
calls were made to drawRuler
to
draw these fifteen rulers, of which 16 were calls to the trivial case.
To the code enclosed I have added a few lines (the lines with variables
test
and max
) that you may use to see how the bars are drawn. You may change max
to different values and thus the
recursion will stop after that many turns. If you increase max
by one each time, you will clearly see what happens, unfortunately you have
to recompile the class each time.
In spite of how the work is actually done within the computer,
many programmers think of the different levels being drawn at the same phase, and then the next level. Either
way the result will be the same. It doesn't matter how many lines there are making recursive calls, there is always
kind of a thread that you may follow that will sketch a tree upside down. As an exercise you can compute the different
values for mid, left, right and level using the sketch. Try to solve the exercise with starting
values as left=0, right=32 and level=4.
As long as we only use common building bricks like JFrame, JPanel,
JButton etc., we never need to worry about Graphics since that is handled automatically within those classes.
But if we like to do something on our own, like we did above, we have to know about one particular method that
we have to use, the paintComponent
method. And we briefly have to know what Graphics is, since it shows up from time
to time.
paintComponent
that in turn calls paint
of the older java.awt.Component.Back in Java 1.x times, without Swing, you maybe used Canvas as
a painting surface. Please, forget about that and make use of the much more powerful Swing components. That way
you will avoid flicker, you will get buffering and some other useful improvements, too. In fact, if you try to
combine the old style with Swing you might get into serious trouble, not necessarily, but stay warned.
Never mind, we wanted to draw something extra on the surface of
such JComponent and thus we have to add instructions to the paintComponent
of the item we choose. Hence the code will look like underneath.
|
paintComponent
is making a call up to the ancestor, using
super
and handing that Graphics variable g
along. Never forget that! How should
the JPanel itself be updated if you take this line away?But hey, what is that Graphics g
then? Consider Graphics a tool box, or a collection of methods to draw lines,
as we do, rectangles, polygons etc. Hence g
is
a reference to that collection and you may use it to get in touch with every method mentioned in the Java API
under java.awt.Graphics. So, when we read g.drawString("A ...
, we can look up drawString
and find that it "Draws the text given by the specified string, using
this graphics context's current font and color. The baseline of the first character is at position (x, y) in this
graphics context's coordinate system". The g
referred
to Graphics that included this useful method.
Where did g
come from initially? The truth is that we never did much to instantiate that g
, but the JVM creates a Graphics object
each time an application using GUI starts, and sends a reference, g
, of that object to every component that has to be made visible. If we don't
have to draw something of our own we never bother our minds with that g
or the paintComponent
, but still it swirl around making the app visible.
What do drawRuler(g, 0, 400, 8)
do? That is actually the first call to the recursive method drawRuler
we have discussed. We pass
the variable g
as well
as the starting parameters. When every recursive call is done we come back and executes the
drawString
and then we are finished.
The only remaining code is the driver that makes everything run.
You will find it enclosed at the end of this column. Please feel yourself free to experiment with the Rec class
and try other objects from the Graphics class. You might use any drawX and fillX method you see there. If you
would like to use colors, you can look up Color. You might write g.setColor(Color.red)
or g.setColor(new Color(0,
0, 255))
for instance. Or try different fonts, found
in Font. Play around as you like to.
If you would like to draw things yourself, you first pick a JPanel
and then you have to override the paintComponent
method
of that class. First line should always be super.paintComponent(g)
. Then you use the reference through g
to reach the collection of methods found in Graphics. We will return to
this topic in a future column.
Complete code to Recursion.java and to Rec.java