Building a right angled triangle with recursion.

Question

I have this homework which required to print asterick to make draw a triangle.

When drawTriangle(0);

 *

When drawTriangle(1);

  *
 **

When drawTriangle(2);

   *
  **
 * *
****

when drawTriangle(3);

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

when drawTriangle(4);

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

when drawTriangle(5);

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

Any advice will be appreciated. Cheers.

Answer 1

A triangle of level x is build by either:

• One asterix if x = 0 (stop condition)
• Or by placing two triangles of level x-1 next to each other, and one on top of the right one

The tricky part involves the printing part. A hint here is that the width/height of a triangle of level x is 2^x...

Answer 2

An OO design with object recursion is as follows;

public class Triangle
{
  int n;
  int size;
  char[][] data;

  public Triangle(int n)
  {
    this.n = n;
    this.size = (int)Math.pow(n,2);
    this.data = new char[size][size];
    fillInData();
  }

  void fillInData()
  {
    if (n == 0)
    {
      //stop case
      data[0][0] = '*';
    }
    else
    {
      //create a triangle with n-1
      //fill in the top left quadrant of data[][] with spaces
      //fill in the other 3 quadrants of data[][] with data[][] from the n-1 triangle
    }
  }
}

I'm sure you can figure out how to print the Triangle;

Answer 3

You've noticed that the height of the triangle is 2^n, I'm sure. So you know you'll need to print out that many rows. You also know you need to remember previous rows, if you're going to copy them in some way, so you know you need to have somewhere to store them - perhaps a Vector?

For a start, creating the triangle leaning over to the left instead of the right is a little easier. Adding the left padding to make it lean right is easy to do once you've got something going.

Start with a single row containing "*": print it, and store that string.

Then do this 'n' times:

• Make the row's you've already got 'square' but adding spaces to their ends until they are all equal length
• For each already existing row ( I mean, not including the new ones we're making below):
  • print it, twice
  • store what you just printed as a new row

That's it. Just add spaces to the left of everything you print out to make it lean over to the right.

(You might notice, once you've done this, that you can do the first step above inside the for loop below it. When you 'make the rows square' you're actually just figuring out a number of spaces to add to each row. By just adding that many spaces between two copies of your current row, in the printout and in the new row that you store, you save printing out [and storing] any unnecessary spaces.)

Here are a couple of helpful string padding functions. padRight will lengthen a string to be n characters wide by adding spaces to the right. padLeft, you guessed it, will add spaces to the left:

  public static String padRight(String s, int n) {
     return String.format("%1$-" + n + "s", s);
  }

  public static String padLeft(String s, int n) {
    return String.format("%1$#" + n + "s", s);
  }

One last opportunity for bonus points: you actually don't need to store the last half of the rows you print out.

Answer 4

Just for fun; here's your problem in Haskell. Might not help you, but I want to share!

import System

dupl t = zipWith (++) t t

pad n row = (replicate ((2 ^ n) - (length row)) ' ') ++ row

createTriangle 0 = ["*"]
createTriangle n = (map (pad n) prec) ++ (dupl prec)
  where prec = createTriangle $ n - 1

drawTriangle = putStr . unlines . createTriangle

main = getArgs >>= drawTriangle . read . (!! 0)

Run with runhaskell thisstuff.hs [number]

Answer 5

import java.util.*;

public class Triangle {

    public void drawTriangle(int scale){
     scale = 1 << scale;
     StringBuilder line = new StringBuilder();
     char t = 0;

     for (int i = 0; i <= scale; i++){
           line.append(" ");
     }
     line.setCharAt(scale, '*');

     for(int i = 0; i < scale; i++){
           System.out.println(line);

     for(int j = scale-i; j <= scale; j++){
                 t = line.charAt(j)==line.charAt(j-1) ? ' ':'*';
                 line.setCharAt(j-1,t);
           }

     }

}

    public static void main(String args[]){
        Triangle t = new Triangle();
        t.drawTriangle(5);
    }
}

This few lines of code is sufficent to achieve that.

Answer 6

Here's a pretty python script...not much pythonic. :(

def triangle(n):
   if n == 0:
      return "*"
   else:
      small = triangle(n-1)
      lines = small.split("\n")
      top = ""
      for line in lines:
         top += len(lines[0])*" " + line + "\n"
      bot = '\n'.join([2*line for line in lines])
      return top + bot


for i in range(5):
   print(triangle(i))

Here's the output

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