java - recursivo - Crea un triángulo de estrellas usando solo recursión

recursividad y el manejo de memoria en java

Question

Necesito escribir un método que se llame como printTriangle(5); . Necesitamos crear un método iterativo y un método recursivo (sin CUALQUIER iteración). El resultado debe verse así:

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

Este código funciona con el iterativo pero no puedo adaptarlo para que sea recursivo.

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

Debo señalar que no puede usar ninguna variable de nivel de clase o ningún método externo.

Answer 1

Creo que esto debería funcionar ... no probado de la parte superior de mi cabeza.

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

Answer 2

Ejemplo en python (solo por prototipos, pero espero que la idea se transmita):

#!/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)

La salida se ve así:

$ python 2717111.py
*
**
***
****
*****

Answer 3

Entonces, necesitas crear un bloque pequeño. ¿Qué información necesita ese bloque? Solo el máximo. Pero la recursión necesita saber en qué línea está ... terminas con un constructor como:

public void printTriangle (int current, int max)

Ahora, usa eso para unir el resto de la recursividad:

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

Ahora, todo lo que tienes que hacer es iniciarlo:

printTriangle(1, 5);

Answer 4

Puede convertir un bucle en una función recursiva como esta:

void printStars(int count) {
    if (count == 0) return;

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

Debería poder hacer una función similar para imprimir líneas.

Answer 5

Puedes hacerlo así:

El método obtiene el número de estrellas como un parámetro. Vamos a llamarlo n.

Entonces eso:

1. se llama recursivamente con n-1.

2. imprime una línea con n estrellas.

Asegúrese de no hacer nada si n == 0.

Answer 6

También puede hacerlo con una única recursión (no tan elegante), de la siguiente manera:

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

La idea es que los parámetros del método representen el estado completo del dibujo.

Tenga en cuenta que el tamaño debe ser mayor que 0.

Answer 7

package playground.tests;

import junit.framework.TestCase;

public class PrintTriangleTest extends TestCase {
    public void testPrintTriangle() throws Exception {
        assertEquals("*/n**/n***/n****/n*****/n", printTriangleRecursive(5, 0, 0));
    }

    private String printTriangleRecursive(int count, int line, int character) {
        if (line == count)
            return "";
        if (character > line)
            return "/n" + printTriangleRecursive(count, line + 1, 0);
        return "*" + printTriangleRecursive(count, line, character + 1);
    }

}

Answer 8

    void trianglePrint(int rows){
            int static currentRow = 1;
            int static currentStar = 1;

            // enter new line in this condition
            // (star > currentrow)  

            if (currentStar > currentRow ){
                currentStar = 1;
                currentRow++;
                cout << endl;
            }

            if (currentRow > rows){
                return; // finish
            }

            cout << "*";
            currentStar++;

            trianglePrint(rows);
        }

Answer 9

Observe en su enfoque iterativo que tiene dos contadores: el primero es qué línea está en line , y el segundo es la posición en la línea en la que se encuentra x . Puede crear una función recursiva que tome dos parámetros y los use como contadores anidados, y y x . Donde disminuyes x hasta que llega a 0, entonces decrementa y establece x = y, hasta que tanto x como y son 0.

También podría observar que cada línea sucesiva en el triángulo es la línea anterior más una estrella. Si su función recursiva devuelve una cadena de estrellas para la línea anterior, la siguiente línea es siempre esa cadena más una estrella más. Entonces, tu código sería algo así como:

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

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

    return p;
 }