Recursively printing a star pattern

Question

For my c++ data structures class our assignment is to print a pattern of stars like this

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

with the number of lines in the pattern determined by the user input. So the pattern above would print if the user enters a 4.

We had a previous assignment where we had to print the opposite pattern, one like this

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

and the above pattern would print if the user enters a 5. This pattern, the one above, I had no problem with. I used a for loop to print the top half, then recursively called the function again, and then the same for loop to print the bottom half in the opposite direction. For reference, here's the code I used for the above pattern:

int main()
{
    int number;                                             
    cout << "Enter the number of lines in the grid: ";      

    cin >> number;                                          
    printStars(number);                                     
    cout << endl << "Grid Pattern Complete - End of Program.";
    return 0;
} // end of main 

void printStars(int num)                        
{
    if (num < 0) cout << endl << "Please enter a non negative number." << endl;

        else{

            if (num == 0) return;               

            else{
            for (int q = 1; q <= num; q++)      
            {cout << "*";}
            cout << endl;

            printStars(num - 1);        

            for (int q = 1; q <= num; q++)      
            {cout << "*";} 

            cout << endl;
        } 
    } 
} // end printStars

This function works like how I want it, so I figured I would use it as a reference to complete the second assignment. The problem I'm having is that, while it was easy enough to complete the first assignment (printing a line of 4 stars, then a line of 3, then a line of 2 , then a line of 1, then all that again in reverse order), I can't seem to figure out how to format the for loops to print the pattern starting with a line of 1 star, then a line of 2, then a line of 3, and so on, until its called recursively and printed again in reverse order.

For reference, this is the code I have (so far) for the second assignment:

int main()
{
    int number;                                             
    cout << "Enter the number of lines in the grid: ";      
    cin >> number;
    printStars(number, 0);                                 

    cout << endl << "Grid Pattern Complete - End of Program.";

    return 0;
}

void printStars(int num, int num2)
{
  if (num2 <= num)
  {

      for (int e = num; e > num2; e--)
      {
          cout << "*";
      }

      cout << endl;

      printStars(num - 1, num2);

  }
}

The only thing this prints is the second half of the pattern;

(If the user enters a 5)

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

And even to make this work, I have to recursively call the function at the end, which is out of order.

I guess I'm just confused on how this recursion is supposed to work but I've been playing with it for hours and I can't seem to reformat it or rearrange it or restructure it so that it prints like I need it to. Can someone give me some guidance? Just maybe write some pseudo code to help me out. This is for school so I need to be able to understand it but I'm really lost right now.

Answer 1

I think the best answer should be if only one recursive function is used -

#include <iostream>

using namespace std;

void recursive(int current, int lastEnter, int limit, bool isLimitReached) {
    cout << "*";
    if(current == lastEnter ) {
        cout << endl;
        current = 0;
        if(isLimitReached == false) 
            lastEnter++;
        else lastEnter--;
    }
    if(current + 1 == limit) {
        isLimitReached = true;
    }
    current++;
    if(!(isLimitReached == true && lastEnter == 0))
        recursive(current, lastEnter, limit, isLimitReached);
}

int main()
{
    int num = 0;
    cout << "Enter max number of stars to be generated : ";
    cin >> num;
    recursive(1, 1, num, false);
    return 0;
}

The code above uses only one recursive function without for/while loops. output -

Enter max number of stars to be generated : 6 
*  
**       
***    
****    
*****   
******  
*****     
****    
***    
**   
*  

Answer 2

For the sake of the exercise - how about a recursive function to print the stars and another to determine the number of stars:

string ReturnStars(int number)
{
  if (number > 1)
    return "*" + ReturnStars(number -1);

  return "*";
}

void PrintStars(int start, int lines)
{
  cout << ReturnStars(start) << endl;

  if (start < lines)
    PrintStars(start + 1, lines);

  cout << ReturnStars(start) << endl;
}

int main()
{
  int numberLines = 1;
  cout << "Please enter a positive number to print a star pattern for: ";
  cin >> numberLines;
  PrintStars(1, numberLines);

  return 0;
}

Example of output:

Answer 3

The straightforward approach if to use the function declared as having only one parameter is the following with using a static local variable in the function

#include <iostream>

void print_stars( size_t n )
{
    static size_t m;

    if ( m++ != n )
    {
        for ( size_t i = 0; i < m; i++ ) std::cout << '*';
        std::cout << std::endl;
        print_stars( n );
    }

    --m;
    for ( size_t i = 0; i < m; i++ ) std::cout << '*';
    std::cout << std::endl;
}

int main() 
{
    while ( true )
    {
        std::cout << "Enter a non-negative number (0-exit): ";

        size_t n = 0;
        std::cin >> n;

        if ( !n ) break;

        std::cout << std::endl;
        print_stars( n );
        std::cout << std::endl;
    }

    return 0;
}

The program output can look like

Enter a non-negative number (0-exit): 4

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


Enter a non-negative number (0-exit): 3

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


Enter a non-negative number (0-exit): 2

*
**
**
*


Enter a non-negative number (0-exit): 1

*
*


Enter a non-negative number (0-exit): 0

If you do not want to use a static variable within the recursive function then instead of it you can apply a trick with standard stream member function width. In this case the recursive function will look the following way

#include <iostream>
#include <iomanip>

void print_stars( size_t n )
{
    std::streamsize m = std::cout.width();

    if ( m++ != n )
    {
        std::cout.width( m );
        std::cout << std::setfill( '*' );
        std::cout << '*' << std::endl;
        std::cout.width( m );
        print_stars( n );
    }

    std::cout.width( m-- );
    std::cout << std::setfill( '*' );
    std::cout << '\n';
}

int main() 
{
    while ( true )
    {
        std::cout << "Enter a non-negative number (0-exit): ";

        size_t n = 0;
        std::cin >> n;

        if ( !n ) break;

        std::cout << std::endl;
        print_stars( n );
        std::cout << std::endl;
    }

    return 0;
}

The output will be the same as above.

P.S. It seems that the only programmer who is able to write the function is me unemployed.:) All others are unable to do this assignment for beginners.:)

Answer 4

If you want to do it recursively, you have to keep in mind that there are multiple states: the state where you're counting up to N, and the state where you're counting back to 1. So if you have to go it recursively, you need to keep track of those extra things:

void printStarsImpl(int count, int initial, int sign)
                    ↑          ↑            ↑
                    current    termination  next step

And this function just has to know which next printStarsImpl() function to call - whether we just call with count + sign, whether we flip sign to -1, or whether we do nothing... all after printing count *'s of course.

The initial call is then:

void printStars(int n) {
    printStarsImpl(1, n, +1);
}

Answer 5

Try this. It is minimally modified version of your code. The upper limit is passed to all recursions and the recursive function calls are performed with the values starting with 1 (only 1 start in the first line):

void printStars(int num, int limit)                         
{
        if (num >limit) return;              
        else{
        for (int q = 1; q <= num; q++)      
        {cout << "*";}
        cout << endl;

        printStars(num +1, limit);        

        for (int q = 1; q <= num; q++)      
        {cout << "*";} 

        cout << endl;
    } 

}

int main()
{        
    int number=5;  
    cin>>number;                                
    printStars(1, number);                                     

    return 0;
} // end of main 

I tested it and the result is correct. The link is:

http://ideone.com/ez6pZ5

ideone result:

Success time: 0 memory: 3144 signal:0

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

Answer 6

You aren't printing out the stars after your recursion call:

void printStars(int num, int num2)
{
  if (num2 < num)
  {

      for (int e = num; e > num2; e--)
      {
          cout << "*";
      }

      cout << endl;

      printStars(num - 1, num2);

      for (int e = num; e > num2; e--)
      {
          cout << "*";
      }

        cout << endl;
  }
}

note the if condition had to change slightly too. I also agree with Thomas, it might make more sense to structure your recursion differently:

void printStars(int num)
{
    for (int i = 1; i <= num; i++)
    {
        cout << "*";
    }

    cout << endl;
}

void printStarsRecursive(int stars)
{
    if (stars == 0)
        return;

    printStars(stars);
    printStarsRecursive(stars-1);
    printStars(stars);
}

int main()
{
    int number;                                             
    cout << "Enter the number of lines in the grid: ";      
    cin >> number;
    printStarsRecursive(number);                                 

    cout << endl << "Grid Pattern Complete - End of Program.";

    return 0;
}

Answer 7

I suggest using two recursive functions, one to print in increasing order and the other to print in decreasing order.

After you get the two functions working, save a copy of the program.

You can then try to create one function the performs both increasing and decreasing orders of stars.