// Example of Recursion - 
// Write a function that prints a triangle:
//   
// triangle(4);		triangle(5);
// 
//     *             *
//    ***           ***
//   *****         *****
//  *******       *******
//               *********

// g++ -o triangles triangless.cpp
//

// This is a trick question !!!!
// Unless you make some assumptions about the maximum size triangle
// you will be asked to draw - you can't write the triangle function
// as a recursive function.
// 
// You can come pretty close, something like this looks very close:


//  void triangle(int n) {
//    if (n==1) {
//      // base case
//      cout << "*" << endl;
//    } else {
//      triangle(n-1,width);	// draw top (which is a smaller triangle)

//      for (int i=0;i<2*n-1;i++)   // draw bottom row of this triangle
//        cout << "*";
//      cout << endl;
//    }
//  }


// the problem is that the above code will produce output that looks like
// this :

// *
// ***
// *****
// *******
// *********
//
// although this is a triangle, it is not what we want. 
//
// the real problem is that we don't know how many spaces to put to
// the left of a triangle unless we know how wide the entire triangle 
// will be (the number of "*"s in the bottom row).
//
// Below is my solution - triangle() is a function that calls
//    rtriangle() which is a recursive function. rtriangle() is given
//    the triangle height, and the maximum width (so it can figure out how
//    far each line must be shifted over to leave room for lines below  



#include <iostream.h>


// recursive function triangles will draw a triangle of
// height n
// 
// The base case is 1 - a triangle of height 1 is just a single
// *.   However, it's not quite that simple. TO draw a triangle of 
// height 1 we need to know where to start (what column), and that
// depends on how large to entire triangle is! 

// SO - we really need a "helper function" that handles the recursion!


// rtriangle(n,width) draws a triangle of height n and adds spaces at the
// beginning of each line so that the center of the triangle will be
// at width/2 (this leaves room so that lines below can be added to 
// finish the triangle.
// 

void rtriangle(int n, int width) {
  if (n==1) {
    // base case - height 1

    // center the single * by printing width/2 spaces

    for (int i=0;i<width/2;i++)
      cout << " ";

    // here is the triangle of height 1
    cout << "*" << endl;

  } else {


    // recursive step - the way to draw a triangle of height n
    // is to first draw a triangle of height n-1, then add the
    // last row.


    // this is the recursive call - draw a triangle of height n-1
    rtriangle(n-1,width);


    // now draw the bottom row

    // first print the right number of spaces
    for (int i=0;i<(width-(2*n-1))/2;i++)
      cout << " ";

    // now add the *s that make up this row
    for (int i=0;i<2*n-1;i++)
      cout << "*";
    cout << endl;
  }
}


// now triangle just calls rtriangle and gives it the right width

 
void triangle(int n) {
  rtriangle(n,2*n-1);
}
 


int main(void) {

  int h;

  cout << "Enter height\n";

  cin >> h;

  triangle(h);

  return(0);
}