Printing asterisk-pattern recursively - Getting wrong output containing repeated parts

Question

I'm trying to print a star-pattern using recursion.

The problem is that when my pattern is printed completely it again starts to print the pattern after a line or two line gaps recursively.

It seems like my base case is correct, where I am doing it wrong?

My code:

public static void printRecursion(int row) {
    int i = 1;
    printRecursion2(row, i);
}

private static void printRecursion2(int row, int i) {
    if (row <= 0) {
        return;
    }

    if (i <= row) {
        System.out.print("* ");
        i++;
        printRecursion2(row, i);
    }

    System.out.println();
    i = 1;
    printRecursion2(row - 1, i);
}

The output I am getting:

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

The output I want:

* * * * 
* * * 
* * 
*

userJ459 · Answer

You are trying to use the same, recursive method to both print a single line and also to print all the lines. It should be split into two recursive methods, i.e. one for printing a single line and another for printing all the lines.

In the below code, method printRow prints a single line, recursively, while method printRecursion prints all the lines – also recursively.

public class Main {

    private static void printRow(int length) {
        if (length == 0) {
            System.out.println();
        }
        else {
            System.out.print("* ");
            printRow(length - 1);
        }
    }

    private static void printRecursion(int row) {
        if (row <= 0) {
            return;
        }
        printRow(row);
        printRecursion(row - 1);
    }

    public static void main(String[] args) {
        printRecursion(3);
    }    
}

The output I get is:

* * * 
* * 
*

In order to understand why your code is failing, you should run it with a debugger. After each recursive call to printRecursion2, in the if(i<=row) in that method, the rest of the method is performed. After printing a single line, you are trying to continue the recursion but for all the lines.

The following code is an attempt to demonstrate what your code is doing. When the recursive call is made, instead of printing a * (asterisk), I increment an iteration variable and print it. After the method terminates, I decrement iteration and print it. Here is the code:

public class Main {
    private static int iteration = 0;

    public static void printRecursion(int row) {
        int i=1;
        printRecursion2(row,i);
    }

    private static void printRecursion2(int row,int i) {
        ++iteration;
        debug();
        if(row<=0)
        {
            return;
        }
        if(i<=row)
        {
            i++;
            printRecursion2(row,i);
            --iteration;
            debug();
        }
        System.out.println();
        i=1;
        printRecursion2(row-1,i);
        --iteration;
        debug();
    }

    private static void debug() {
        for (int i = 0; i < iteration; i++) {
            System.out.print(" ");
        }
        System.out.println("Iteration: " + iteration);
    }

    public static void main(String[] args) {
        printRecursion(3);
    }    
}

Here is the output:
(I have added comments to the first few lines in the hope that it helps you visualize the flow of your code.)

 Iteration: 1 <- called from 'printRecursion'
  Iteration: 2 <- prints first * in first row
   Iteration: 3 <- prints second * in first row
    Iteration: 4 <- prints third * in first row

     Iteration: 5 <- 'row' decremented ('row' == 2), 'i' reset to 1
      Iteration: 6 <- prints first * in second row
       Iteration: 7 <- prints second * in second row

        Iteration: 8 <- 'row' decremented ('row' == 1), 'i' reset to 1
         Iteration: 9 <- prints first * in third row

          Iteration: 10 <- 'row' decremented ('row' == 0 so no more recursive calls), 'i' reset to 1
         Iteration: 9 <- return from recursive call
        Iteration: 8 <- return from recursive call

         Iteration: 9 <- 'row' decremented, 'i' reset to 1
        Iteration: 8

         Iteration: 9
        Iteration: 8
       Iteration: 7
      Iteration: 6

       Iteration: 7
        Iteration: 8

         Iteration: 9
        Iteration: 8
       Iteration: 7

        Iteration: 8
       Iteration: 7
      Iteration: 6
     Iteration: 5

      Iteration: 6
       Iteration: 7

        Iteration: 8
       Iteration: 7
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5
    Iteration: 4
   Iteration: 3

    Iteration: 4
     Iteration: 5
      Iteration: 6

       Iteration: 7
        Iteration: 8

         Iteration: 9
        Iteration: 8
       Iteration: 7

        Iteration: 8
       Iteration: 7
      Iteration: 6
     Iteration: 5

      Iteration: 6
       Iteration: 7

        Iteration: 8
       Iteration: 7
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5
    Iteration: 4

     Iteration: 5
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5

      Iteration: 6
     Iteration: 5
    Iteration: 4
   Iteration: 3
  Iteration: 2

   Iteration: 3
    Iteration: 4
     Iteration: 5

      Iteration: 6
       Iteration: 7

        Iteration: 8
       Iteration: 7
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5
    Iteration: 4

     Iteration: 5
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5

      Iteration: 6
     Iteration: 5
    Iteration: 4
   Iteration: 3

    Iteration: 4
     Iteration: 5

      Iteration: 6
     Iteration: 5
    Iteration: 4

     Iteration: 5
    Iteration: 4
   Iteration: 3
  Iteration: 2
 Iteration: 1

  Iteration: 2
   Iteration: 3
    Iteration: 4

     Iteration: 5
      Iteration: 6

       Iteration: 7
      Iteration: 6
     Iteration: 5

      Iteration: 6
     Iteration: 5
    Iteration: 4
   Iteration: 3

    Iteration: 4
     Iteration: 5

      Iteration: 6
     Iteration: 5
    Iteration: 4

     Iteration: 5
    Iteration: 4
   Iteration: 3
  Iteration: 2

   Iteration: 3
    Iteration: 4

     Iteration: 5
    Iteration: 4
   Iteration: 3

    Iteration: 4
   Iteration: 3
  Iteration: 2
 Iteration: 1

I added printing of the values of row and i to the above code by changing method debug to the following:

private static void debug(int row, int i) {
    for (int j = 0; j < iteration; j++) {
        System.out.print(" ");
    }
    System.out.printf("Iteration %d: row = %d , i = %d%n", iteration, row, i);
}

Here is the modified output:

 Iteration 1: row = 3 , i = 1
  Iteration 2: row = 3 , i = 2
   Iteration 3: row = 3 , i = 3
    Iteration 4: row = 3 , i = 4

     Iteration 5: row = 2 , i = 1
      Iteration 6: row = 2 , i = 2
       Iteration 7: row = 2 , i = 3

        Iteration 8: row = 1 , i = 1
         Iteration 9: row = 1 , i = 2

          Iteration 10: row = 0 , i = 1
         Iteration 9: row = 1 , i = 1
        Iteration 8: row = 1 , i = 2

         Iteration 9: row = 0 , i = 1
        Iteration 8: row = 1 , i = 1
       Iteration 7: row = 2 , i = 1
      Iteration 6: row = 2 , i = 3

       Iteration 7: row = 1 , i = 1
        Iteration 8: row = 1 , i = 2

         Iteration 9: row = 0 , i = 1
        Iteration 8: row = 1 , i = 1
       Iteration 7: row = 1 , i = 2

        Iteration 8: row = 0 , i = 1
       Iteration 7: row = 1 , i = 1
      Iteration 6: row = 2 , i = 1
     Iteration 5: row = 2 , i = 2

      Iteration 6: row = 1 , i = 1
       Iteration 7: row = 1 , i = 2

        Iteration 8: row = 0 , i = 1
       Iteration 7: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 2 , i = 1
    Iteration 4: row = 3 , i = 1
   Iteration 3: row = 3 , i = 4

    Iteration 4: row = 2 , i = 1
     Iteration 5: row = 2 , i = 2
      Iteration 6: row = 2 , i = 3

       Iteration 7: row = 1 , i = 1
        Iteration 8: row = 1 , i = 2

         Iteration 9: row = 0 , i = 1
        Iteration 8: row = 1 , i = 1
       Iteration 7: row = 1 , i = 2

        Iteration 8: row = 0 , i = 1
       Iteration 7: row = 1 , i = 1
      Iteration 6: row = 2 , i = 1
     Iteration 5: row = 2 , i = 3

      Iteration 6: row = 1 , i = 1
       Iteration 7: row = 1 , i = 2

        Iteration 8: row = 0 , i = 1
       Iteration 7: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 2 , i = 1
    Iteration 4: row = 2 , i = 2

     Iteration 5: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 1 , i = 2

      Iteration 6: row = 0 , i = 1
     Iteration 5: row = 1 , i = 1
    Iteration 4: row = 2 , i = 1
   Iteration 3: row = 3 , i = 1
  Iteration 2: row = 3 , i = 3

   Iteration 3: row = 2 , i = 1
    Iteration 4: row = 2 , i = 2
     Iteration 5: row = 2 , i = 3

      Iteration 6: row = 1 , i = 1
       Iteration 7: row = 1 , i = 2

        Iteration 8: row = 0 , i = 1
       Iteration 7: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 2 , i = 1
    Iteration 4: row = 2 , i = 3

     Iteration 5: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 1 , i = 2

      Iteration 6: row = 0 , i = 1
     Iteration 5: row = 1 , i = 1
    Iteration 4: row = 2 , i = 1
   Iteration 3: row = 2 , i = 2

    Iteration 4: row = 1 , i = 1
     Iteration 5: row = 1 , i = 2

      Iteration 6: row = 0 , i = 1
     Iteration 5: row = 1 , i = 1
    Iteration 4: row = 1 , i = 2

     Iteration 5: row = 0 , i = 1
    Iteration 4: row = 1 , i = 1
   Iteration 3: row = 2 , i = 1
  Iteration 2: row = 3 , i = 1
 Iteration 1: row = 3 , i = 2

  Iteration 2: row = 2 , i = 1
   Iteration 3: row = 2 , i = 2
    Iteration 4: row = 2 , i = 3

     Iteration 5: row = 1 , i = 1
      Iteration 6: row = 1 , i = 2

       Iteration 7: row = 0 , i = 1
      Iteration 6: row = 1 , i = 1
     Iteration 5: row = 1 , i = 2

      Iteration 6: row = 0 , i = 1
     Iteration 5: row = 1 , i = 1
    Iteration 4: row = 2 , i = 1
   Iteration 3: row = 2 , i = 3

    Iteration 4: row = 1 , i = 1
     Iteration 5: row = 1 , i = 2

      Iteration 6: row = 0 , i = 1
     Iteration 5: row = 1 , i = 1
    Iteration 4: row = 1 , i = 2

     Iteration 5: row = 0 , i = 1
    Iteration 4: row = 1 , i = 1
   Iteration 3: row = 2 , i = 1
  Iteration 2: row = 2 , i = 2

   Iteration 3: row = 1 , i = 1
    Iteration 4: row = 1 , i = 2

     Iteration 5: row = 0 , i = 1
    Iteration 4: row = 1 , i = 1
   Iteration 3: row = 1 , i = 2

    Iteration 4: row = 0 , i = 1
   Iteration 3: row = 1 , i = 1
  Iteration 2: row = 2 , i = 1
 Iteration 1: row = 3 , i = 1

Alexander Ivanchenko · Answer

The problem is rooted in the way you've designed your methods. Although you have 2 of them, effectively only one of them just wraps the call to the second method, which is responsible for both: printing a separate row, and printing each asterisk in a row.

For that reason, while you a calling the method in order to print a single asterisk, in fact it spawns a new brunch of recursive calls.

There are two ways to avoid that:

You can implement this task with a single method, printing each row in a loop:

public static void printRecursion(int row) {
    if (row <= 0) return;

    for (int i = 0; i < row; i++) { // printing a row of asterisks
        System.out.print("* ");
    }

    System.out.println(); // advancing output to the next row

    printRecursion(row - 1);
}

Or if you're not allowed to use loops. You can introduce a helper-method responsible for printing a row of asterisks:

public static void printRecursion(int row) {
    if (row <= 0) return;
    
    printRow(row);        // printing a row of asterisks
    
    System.out.println(); // advancing output to the next row
    
    printRecursion(row - 1);
}

public static void printRow(int col) {
    if (col <= 0) return;
    
    System.out.print("* ");

    printRow(col - 1);
}

main()

public static void main(String[] args) {
    printRecursion(4);
}

Output:

* * * * 
* * * 
* * 
*

userR6m6 · Answer

remove the first call to printRecursion2 and change the second if to a while, like

private static void printRecursion2(int row,int i) {

    if(row<=0)
    {
        return;
    }
    while(i<=row)
    {
        System.out.print("* ");
        i++;
    }
    System.out.println();
    i=1;
    printRecursion2(row-1,i);
}

but an easier way would be to have this single function:

public static void printRecursion(int row) {
    if (row <= 0) return;
    System.out.println("* ".repeat(row));
    printRecursion(row - 1);
}

Printing asterisk-pattern recursively - Getting wrong output containing repeated parts

3 Answers