logo标签列表

使用递归创建一个星号三角形

javarecursion
8
我需要编写一个方法，类似于printTriangle(5);。我们需要创建一个迭代方法和一个递归方法（不使用任何迭代）。输出应该像这样：
*
**
***
****
*****

这段代码在迭代方式下可以工作，但我无法将其改为递归方式。

public void printTriangle (int count) {
    int line = 1;
    while(line <= count) {
        for(int x = 1; x <= line; x++) {
            System.out.print("*");
        }
        System.out.print("\n");
        line++;
    }
}

我需要说明的是，您不能使用任何类级变量或外部方法。

8
这是一份家庭作业吗？ - DJ.
@DJ。是的，没错。这是22章以来我第一次遇到问题。@mobrule：那跟什么有关系吗？我尝试过使用格式化字符串，但似乎Java不支持自定义填充字符。 - Alec Gorge
为什么在迭代版本中要将while循环和for循环结合起来？使用两个嵌套的for循环会更加简洁（也许更容易转换为递归）。 - Justin Ardini
我本来可以做得更快，但我的教授说他想要清晰度而不是性能（我觉得他只是懒）。 - Alec Gorge
参见：http://stackoverflow.com/questions/2498039/printing-a-sideways-triangle-in-java/2498161#2498161 - polygenelubricants
13个回答
18

注意在你的迭代方法中，你有两个计数器：第一个是你所在的行数line，第二个是你在该行上的位置x。你可以创建一个递归函数，它接受两个参数并将它们用作嵌套计数器y和x。在该函数中，把x递减直到为0，然后将y递减，并设置x=y，直到x和y都为0。

你还可以注意到三角形中的每一行都比前一行多一个星号。如果你的递归函数返回前一行的星号字符串，则下一行总是该字符串加上一个星号。所以，你的代码会像下面这样：

public String printTriangle (int count) {
    if( count <= 0 ) return "";

    String p = printTriangle(count - 1);
    p = p + "*";
    System.out.println(p);

    return p;
 }
1
哇，我简直不敢相信我没想到那个。我认为我被扔掉了，因为我假设它必须返回void，因为返回任何东西都没有意义。干得好，谢谢！另外，解释得很好。 - Alec Gorge
这是正确的解决方案。非常聪明！ :-) 一个无关的改进：两个打印语句可以被一个 System.out.println(p); 取代。 - Péter Török
+1 因为比我的解决方案更优雅 :) 很好地利用了返回值。 - Eyal Schneider
7

以下是 Python 的示例（仅用于原型设计，但我希望您能理解这个想法）：

#!/usr/bin/env python

def printTriangle(n):
    if n > 1:
        printTriangle(n - 1)
    # now that we reached 1, we can start printing out the stars 
    # as we climb out the stack ...
    print '*' * n

if __name__ == '__main__':
    printTriangle(5)

输出结果如下：

$ python 2717111.py
*
**
***
****
*****
2
我怀疑那会被认为是迭代。 - SLaks
虽然有效，但对于Java并没有太大帮助 :) - Alec Gorge
3
您可以将循环转换为递归函数，方法如下：
void printStars(int count) {
    if (count == 0) return;

    System.out.print("*");
    printStars(count - 1);
}
printStars(5);    //Prints 5 stars

你应该能够编写类似的函数来打印行。
1
这是一个打印出1行的编程内容。这个任务要求在一个方法中完成整个三角形的赋值，所以让我感到困惑。 - Alec Gorge
1
然后你只需要弄清楚在哪里打印换行符。 - Sam Holder
你需要编写一个单独的递归函数来调用 printStars。 - SLaks
这种方法没有任何问题。如果我们被允许使用两个方法来解决问题，那就没有问题了。但是我们只能使用一个方法。因此，我需要另一种方法，调用printStars然后打印\n，然后增加下一行打印的星号数量——而这是不被允许的。 - Alec Gorge
问题说必须像printTriangle(5)这样调用，这就排除了有2个参数的可能性。 - Sam Holder
显示剩余2条评论
2
你也可以使用单个（不太优雅的）递归来完成，如下所示：
public static void printTriangle (int leftInLine, int currLineSize, int leftLinesCount) {
    if (leftLinesCount == 0)
        return;
    if (leftInLine == 0){ //Completed current line?
        System.out.println();
        printTriangle(currLineSize+1, currLineSize+1, leftLinesCount-1);
    }else{
        System.out.print("*");
        printTriangle(leftInLine-1,currLineSize,leftLinesCount);
    }
}

public static void printTriangle(int size){
    printTriangle(1, 1, size);
}

这个方法的参数表示完整的绘制状态。

注意，尺寸必须大于0。

为了更好地理解简单的递归，使用递归辅助方法打印每一行可能更清晰。不过这样也可以。 :) - Justin Ardini
谢谢，这个有效。我担心我可能不得不使用多参数方法，因为我的教授一直告诉我重载方法有多糟糕（我觉得它非常有用）。希望他能接受这个。@Justin，必须是一个方法。虽然有点牵强，但足够接近了。 - Alec Gorge
0
#include<iostream>
using namespace std;
 void ll__(int x){
  char static c = '0'; // character c will determine when to put newline
  if(!x){
    if(c=='1'){
      cout<<'\n';
    }
    return;
  }
  if(c=='0'){
    ll__(x-1); //  rows to be called in the stack and differentiated by character '0'
  }
  if(x==1 && c=='0'){
   cout<<'*';
  }else{  // columns to be printed in every row as per the row number in the stack
   c = '1';
   ll__(x-1);
   cout<< '*';
  }
}

int main(){
//writes code here
 ll__(5);
 exit(0);
}
请在代码答案中包含一些描述 - William Baker Morrison
0

你可以像这样做：

该方法将星号数量作为参数传入，我们称之为n。

然后它：

  1. 用 n-1 作为参数递归调用自身。

  2. 打印一行有 n 个星号的内容。

如果 n == 0 则不执行任何操作。

打印一行n个星号需要迭代，除非单独定义递归。 - Michael Petito
0
我发现最好的方法是：
    public static void printTriangle(int x) {
        if(x == 0) {
            return;
        }
        printTriangle(x-1);
        printStars(x);
    }
-1

包 com.company;

    public class practise7 { 
    static void star1(int n){
            if(n>0){
                for(int i = 0; i<n; i++){
    
                    System.out.print("*");
                }
                System.out.println("");
                star1(n-1);
            }
    
        }
      public static void main(String[] args) {
    star1(4); 
}
}

打印正向星形图案

package com. company;
        
        public class practise7 { 
        static void star1(int n){
                if(n>0){
                    star1(n-1);
                    for(int i = 0; i<n; i++){
        
                        System.out.print("*");
                    }
                    System.out.println("");
                    
                }
        
            }
          public static void main(String[] args) {
        star1(4); 
    }
    }
请问您能否留下一条评论，描述一下您的解决方案（以及为什么它比之前的更好）？ - pedrohreis
1
你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心中找到有关如何编写良好答案的更多信息。 - Community
-1

我认为这应该可以工作...只是脑海中未经测试。

public void printTriangle(int count)
{    
    if (count == 0) return;
    printTriangle(count - 1);
    for (int x = 1; x <= count; x++) { 
        System.out.print("*"); 
    }
    System.out.print("\n"); 
}
-1 OP要求一个没有任何迭代的递归方法。 - Péter Török
哎呀，我没注意到“任何迭代”这部分... 我也没想到你可以使用多个方法，但是被接受的答案确实可以 :) - Kelsey
方法重载是我认为我们能够接近的最好方式。 - Alec Gorge
-1

所以，您需要创建一个小的代码块。那个代码块需要什么信息？只需要最大值即可。但递归需要知道它所在的行...... 最终得到一个构造函数:

public void printTriangle (int current, int max)

现在，使用它来组合递归的其余部分：
public void printTriangle (int current, int max)
{ 
    if (current <= max) 
    { 
         // Draw the line of stars...
         for (int x=0; x<current; x++)
         {
             System.out.print("*")
         }
         // add a newline
         System.out.print("\n"); 

         // Do it again for the next line, but make it 1-bigger
         printTriangle(current + 1, max);
    } 
}

现在，你所要做的就是启动它：

printTriangle(1, 5);
但它具有迭代。它需要绝对没有迭代。 - Alec Gorge
啊..错过了那一部分。在这种情况下，您只需要有一个第二个迭代函数...虽然标记为“已回答”的那个非常聪明。 - Jerry
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接