递归打印星号图案

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.

- Dariani Disani

---

这个任务要求使用递归吗？似乎不用递归也很容易完成。 - dwcanillas

@dwcanillas 是的，这个任务要求使用递归。这是唯一正确完成它的方法。 - Dariani Disani

只是指出一个打印样式的函数不应该假设参数值来自何处。您应该能够无缝地使用此函数，无论参数来自文件、硬编码等。输入验证应与输入一起处理。 - chris

@DarianiDisani：我对你的代码进行了一些小修改，并给出了答案。它如预期地工作。与你一样，它使用了一个额外参数的递归。我已在ideone.com上测试过，并在我的回答中包含了链接和结果。 - erol yeniaras

Answer 1

试试这个。这是你的代码经过最小修改后的版本。上限被传递到所有递归中，递归函数调用使用从1开始的值（只有第一行开始的1）：

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 

我测试过了，结果是正确的。链接如下：

http://ideone.com/ez6pZ5

ideone 结果：

Success time: 0 memory: 3144 signal:0

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

- erol yeniaras

---

这个有效了，我稍微调整了一下以满足要求，但它完美地工作了，谢谢。 - Dariani Disani

Answer 2

为了练习，如何编写一个递归函数来打印星号，另一个函数用于确定星号的数量：

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;
}

输出示例：

- RooiWillie

Answer 3

在递归调用后，您没有打印出星号：

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;
  }
}

注意if条件也必须稍微更改。我也同意Thomas的观点，可能更合理的是以不同的方式构建递归：

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;
}

- dwcanillas

Answer 4

如果你想要递归地实现它，你必须记住有多个状态：一个是计数到 N 的状态，另一个是计数回到 1 的状态。因此，如果你要递归地实现它，你需要跟踪这些额外的东西：

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

而这个函数只需要知道要调用哪个下一个printStarsImpl()函数 - 不管是我们仅使用count + sign进行调用，还是将sign翻转为-1，或者我们什么都不做...当然，所有这些都在打印count个*之后进行。

然后进行最初的调用：

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

- Barry

Answer 5

如果使用仅声明一个参数的函数的直接方法是在函数中使用静态局部变量，如下所示：

#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;
}

程序的输出可能如下所示

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

如果你不想在递归函数中使用静态变量，那么你可以使用标准流成员函数width的技巧来代替它。在这种情况下，递归函数看起来如下：

#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;
}

输出将与上面相同。

P.S. 看来唯一能编写该函数的程序员是我这个失业者。:) 其他人都无法完成这个初学者的任务。:)

- Vlad from Moscow

Answer 6

我建议使用两个递归函数，一个按升序打印，另一个按降序打印。

在你让这两个函数正常工作之后，保存一份程序的副本。

然后，你可以尝试创建一个函数，它可以执行星号的升序和降序排列。

- Thomas Matthews

---

我不确定是否可以使用两个递归函数提交，因为他已经解释过你只需要一个就可以了。 - Dariani Disani

Answer 7

我认为最好的答案应该是只使用一个递归函数 -

#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;
}

上面的代码仅使用一个递归函数而没有for/while循环。 输出 -

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

- sahossaini