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.

Could you post some code that works for `drawTriangle(0)`? What exactly do you need help with? — Ishtar, Oct 08 '10 at 09:40
You can see the pattern, can't you? At each level copy what you've got three times leaving a gap in the top left corner. So start with a buffer that's a single line with a single star then at each level map every line L to both len(L) spaces + L and L + L and assemble. But that's an iterative operation really - I don't see the need or use for recursion, and given you're building triangles side-by-side in text I can't see any easy way to shoehorn it in either. Or is this graphics? — Rup, Oct 08 '10 at 09:42
@Rup this qns is under recursion and they required this to be done in recursion. Anyway, triangle 5 is made up of many some triangle 4, triangle 3 and triangle 2. Still the base line is still triangle 2 — Derek Long, Oct 08 '10 at 09:58
dont you realised that the triangle resembles the fibonachi diagram? — Derek Long, Oct 08 '10 at 10:01
@Derek: If you need the logic and not the code you should probably mention so in the question itself, rather than in the comments. — Grodriguez, Oct 08 '10 at 12:46
@Grodriguez he says up-front that it's homework though - it's generally accepted we don't give complete code answers for homework questions. — Rup, Oct 08 '10 at 16:43
@Rup, yes, I know, but asking for hints about the logic is different than asking for hints about the code; nothing wrong with either -- I just suggested that the question could be clarified. — Grodriguez, Oct 08 '10 at 17:25

score 3 · Answer 1 · answered Oct 08 '10 at 11:00

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;

score 2 · Answer 2 · answered Oct 08 '10 at 09:43

2

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...

answered Oct 08 '10 at 09:43

Jochem

2,995
16
18

My answer follows this pattern :) – st0le Oct 31 '10 at 04:52

sje397 · Accepted Answer · 2010-10-08T11:19:00.973

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.

@Qwerky: Vector is appropriate. Otherwise, you may as well go the whole hog and just use arrays of chars and no Strings. — sje397, Oct 08 '10 at 14:18
http://stackoverflow.com/questions/1386275/why-java-vector-class-is-considered-obsolete-or-deprecated — Qwerky, Oct 08 '10 at 14:35

ase · Answer 4 · 2010-10-30T18:19:25.780

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]

score 1 · Answer 5 · answered Oct 31 '10 at 04:51

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

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

score 0 · Answer 6 · answered Oct 28 '10 at 05:36

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.

Building a right angled triangle with recursion

6 Answers6