Printing a Bottom-Righthand Triangle

Loops within loops

A common exercise when you are starting to learn to program is writing a program that will print a right-angled triangle made up of stars. There are four possible orientations of the triangle, with the right-angle in the bottom lefthand corner (this is the easiest to do), top lefthand corner, top righthand corner, and bottom righthand corner. These notes will consider writing a program to print a bottom righthand triangle.

First of all, note the importance of generalisation. A program to print a bottom righthand triangle of size 5 is easy to write:

class TriBRSize5only
{
  public static main(String[] args)
  {
   System.out.println("    *");
   System.out.println("   **");
   System.out.println("  ***");
   System.out.println(" ****");
   System.out.println("*****");
  }
}

but this is not very useful as we have to write a new program for every size of triangle. For maximum flexibility, we could put the code that prints the triangle in a separate method, with its size as a parameter, as in:

class TriBR
{
 // Print a bottom-right right-angled triangle of stars,
 // prompt for its size

 public static void main(String[] args) throws IOException
 {
  int size;
  BufferedReader in = Text.open(System.in);
  System.out.print("Enter the size of triangle: ");
  size=Text.readInt(in);
  print(size);
 }

 public static void print(int size)
 {
  Code to print bottom-right triangle of size size
 }

}

Then, if we wanted to print a bottom-right triangle of size 6, we need only use the call TriBr.print(6), if we wanted to print a bottom-right triangle of size 42, we need only use the call TriBr.print(42), and so on. The main method in class TriBR allows us to test the print method - it is called when we enter java TriBR into a Unix window, and prompts for the size required.

For simplicity, however, we will keep the code for writing the triangle in the main method, but generalise it by having the size expressed as a constant which can be altered as necessary. So we have:

class TriBR
{
 // Print a bottom-right right-angled triangle of stars

 static int SIZE=5;
 
 public static void main(String[] args)
 {
  code for writing a bottom-right triangle of size SIZE
 }

}

There is no need for the import java.io.* bit or the throws IOException part since these were only needed to manage reading in the size from the command window.

Here is a bottom-right triangle of size 5:

    *
   **
  ***
 ****
*****

The first thing to note is that standard printing in the command window is from left to right, one line at a time. Also you have to actually print a new line character to start printing on the next line. If spaces were represented by "·" and newlines by "«" what we actually are printing is:

····*«
···**«
··***«
·****«
*****«

So there is a pattern here:

Print 4 spaces then 1 stars then 1 newline
Print 3 spaces then 2 stars then 1 newline
Print 2 spaces then 3 stars then 1 newline
Print 1 spaces then 4 stars then 1 newline
Print 0 spaces then 5 stars then 1 newline

To consider how to deal with this, first we need to remember the general rule for repetition in Java. To do something n times, we can use a for loop of the form:

for(int i=1; i<=n; i++)
   dosomething

where dosomething is the code for whatever we want to do, and i is a new variable name. What we actually want to do is print the ith line of the triangle. We need to see a pattern in the description of each line so we can generalise it. It shouldn't be too hard to see that on line i we print SIZE-i spaces, followed by i stars followed by a newline. So in this case our dosomething is:

print SIZE-i spaces
print i stars
print a newline

To print one star we use

System.out.print("*")

so to print i stars, we use:

for(int j=1; j<=i; j++)
   System.out.print("*");

Since the variable i was already in use, we introduced a new variable j. Similarly, the code to print Size-i spaces is:

for(int j=1;j<=SIZE-i;j++)
   System.out.print(" ");

The code to print a single newline character is:

System.out.println();

Putting this all together means the following will work to print a bottom-right triangle:

class TriBR
{
 // Print a bottom-right right-angled triangle of stars, of size SIZE

 static final int SIZE=5;

 public static void main(String[] args)
 {
  for(int i=1;i<=SIZE;i++)
     {
      for(int j=1;j<=SIZE-i;j++)
         System.out.print(" ");
      for(int j=1;j<=i;j++)
         System.out.print("*");
      System.out.println();
     }
 }
}

In Java, like C, it's common for counting to start at 0 rather than 1, so the following is used to do something n times:

for(int i=0; i<n; i++)
   dosomething

In this case, if we count the first line of the triangle as line 0, we print SIZE-i-1 spaces followed by i+1 stars and a newline, so that would give us the code for main:

 public static void main(String[] args)
 {
  for(int i=0;i<SIZE;i++)
     {
      for(int j=0;j<SIZE-i-1;j++)
         System.out.print(" ");
      for(int j=0;j<i+1;j++)
         System.out.print("*");
      System.out.println();
     }
 }

We might also consider using more meaningful variable name than i and j. For example:

 public static void main(String[] args)
 {
  int row,column;
  for(row=1;row<=SIZE;row++)
     {
      for(column=1;column<=SIZE-row;column++)
         System.out.print(" ");
      for(;column<=SIZE;column++)
         System.out.print("*");
      System.out.println();
     }

Another change made here is to carry on the value of the variable column from the for loop on the sixth and seventh lines to the for loop following it on the eighth and ninth lines, which means the condition used in this for loop is different.

All these variations work in exactly the same way, so the general rule would be to write the code in whichever way you think makes it most obvious what it does.

Doing the work in a method

If you get confused by having a loop working inside a loop, one way to break up the program into manageable chunks would be to use separate methods to do parts of it. Remember that we wanted to print a row SIZE times. So we could have a separate method for printing the ith row. This would make our program:

class TriBR1
{
 // Print a bottom-right right-angled triangle of stars, of size SIZE

 static final int SIZE=5;

 public static void main(String[] args)
 {
  for(int i=0;i<SIZE;i++)
     printRow(i);
 }

 private static void printRow(int i)
 {
  code to print SIZE-i-1 spaces
  code to print i+1 stars
  code to print a newline
 }
}

The code to print a certain number of stars or spaces could be generalised to code to print any string given as one argument a number of times given as a second argument. This would make our complete program:

class TriBR1
{
 // Print a bottom-right right-angled triangle of stars, of size SIZE

 static final int SIZE=5;

 public static void main(String[] args)
 {
  for(int i=0;i<SIZE;i++)
     printRow(i);
 }

 private static void printRow(int i)
 {
  printNTimes(SIZE-i-1," ");
  printNTimes(i+1,"*");
  System.out.println();
 }

 private static void printNTimes(int n,String s)
 {
  for(int i=0;i<n;i++)
     System.out.print(s);
 }

}

The methods have return type void because they do not return a value but instead do something, that is print the appropriate text. An alternative would be to have the methods return strings to be printed directly in the main method. A program working in this way would look like:

class TriBR2
{
 // Print a bottom-right right-angled triangle of stars, of size SIZE

 static final int SIZE=5;

 public static void main(String[] args)
 {
  for(int i=0;i<SIZE;i++)
     System.out.println(row(i));
 }

 private static String row(int i)
 {
  String spaces,stars;
  spaces=repeat(SIZE-i-1,' ');
  stars=repeat(i+1,'*');
  return spaces+stars;
 }

 private static String repeat(int n,char ch)
 {
  String s="";
  for(int i=0;i<n;i++)
     s+=ch;
  return s;
 }

}

The Java call System.out.println(something) prints the value of the expression something (or the string equivalent if it is not already of type String) followed by a newline character, so that deals with the newline. The method repeat here takes a single character rather than a string as its input. It starts off with an empty string and then joins the character to that string repeatedly, showing that += works with strings (with + with strings meaning concatenation) as well as numbers. The methods row and repeat are declared as private, indicating that they are intended for use only within the class TriBR2 and indeed cannot be accessed from outside that class.

Replacing iteration by recursion

Programming with loops is known as iteration, (the verb "to iterate" being defined in my dictionary as meaning "to repeat"). There is an alternative way of dealing with problems involving repetition of actions which does not involve using loops. The alternative method is known as recursion (from a verb "to recurse" which before the days of computers was so rare that it doesn't occur in my dictionary, the closest to it being the heraldic term "recursant" meaning "turned backwards"). In simple examples like the one we're considering here, it's best not to use recursion. Recursion involves a lot of method calling, and the work done by the computer underneath when a method is called is a lot more than when a counter variable is changed in iteration. The importance of recursion is that it has widespread application, and in many cases recursive versions of programs are easier to develop and understand than iterative ones. In the triangle examples here recursive versions are discussed just as a way of introducing the idea.

The basis of recursion is that a method may often be defined in terms of itself. Hence the joke that when the dictionary definition of "recursion" is written, it should read "see under recursion". In fact this is not such a strange idea as it first seems. It's often the case that when we solve a problem we break it down into smaller versions of the same problem. If I'm trying to plan a route from A to B, for example, it's often a good idea to pick somewhere in between, C, and then plan a route from A to C and a route from C to B. I've broken down my route-planning problem into two smaller route-planning problems, which being smaller are easier for me to tackle. Then, either my route from A to C is so obvious that I don't have to plan it any further, or I can pick another midpoint between A and C, D, and repeat the process.

The problem of making a string which is n copies of a character can be tackled recursively. A string which is n copies of a character can be obtained by joining the character to a string which is n-1 copies of the character. That's unless n is 0, in which case the string is the empty string, written "" in Java. The case when n is 0 is the equivalent to the case in my route-planning where the route between the two places I am thinking of is so simple I don't have to think any further about it. This is called the base case, and obviously if you are going to use recursion you are going to have to get to a base case eventually so that you don't divide up your problem forever. To put it another way, it would be silly to try to solve a problem by always solving a bigger problem as you'd never stop solving it; you should always make sure when you're solving a problem recursively you do it in terms of smaller versions of the same problem.

So here's a recursive version of repeat:

 private static String repeat(int n,char ch)
 {
  if(n==0)
     return "";
  else
     return repeat(n-1,ch)+ch;
 }

Put it in the place of the previous version of repeat and it will work just as well.

Having considered this, you might like to consider that the whole triangle problem could be tackled recursively. Think of it this way - how do your print a bottom-right triangle of size 5? One way is to print a bottom-right triangle of size 4 shifted one space to the left:

····*«
···**«
··***«
·****«

followed by a line with 5 stars:

*****«

That is almost a recursive definition. We can make it recursive by changing the original problem to one of "print a bottom-right triangle of size SIZE shifted n spaces to the right". This can be done by printing a bottom-right triangle of size SIZE-1 shifted n+1 spaces to the right, followed by a line consisting of n spaces and SIZE stars. Now that is a recursive definition and can be translated directly to a recursive program:

class TriBR3
{
 // Print a bottom-right right-angled triangle of stars, of size SIZE

 static final int SIZE=5;
 
 public static void main(String[] args)
 {
  printShiftedBRTri(0,SIZE);
 }

 private static void printShiftedBRTri(int shift,int size)
 {
  if(size>0)
     {
      printShiftedBRTri(shift+1,size-1);
      System.out.println(repeat(shift,' ')+repeat(size,'*'));
     }
 }

 private static String repeat(int n,char ch)
 {
  if(n==0)
     return "";
  else
     return repeat(n-1,ch)+ch;
 }

}

The base case is when the size of the triangle is 0, in which case nothing is done.

As an exercise, you could consider how you would write recursive methods that would print the right-angled triangles with their right-angles in the other three possible places.

The code for the examples in this section can be found in:

/import/teaching/BSc/1st/ItP/triangles

Matthew Huntbach

These notes were produced as part of the course Introduction to Programming as it was given in the Department of Computer Science at Queen Mary, University of London during the academic years 1998-2001.

Last modified: 23 Oct 1998