2
\$\begingroup\$

I wrote a program to print the following pattern using recursion to hands on recursion and my output is perfect but I want to know another and the most optimized approach for this.

This is the sample output of my program if we insert n = 5:

54321  
4321  
321  
21  
1

public class JavaApplication2 {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();        
        printNumber(n,n);
        scan.close();
    }
    static int printNumber(int n,int a) {
            if(a == 0)
                return 0;
            else
            {  
               System.out.print(n);

               if(n==1)
               {
                   System.out.println();
                   --a;
                   n = a +1;  
               }
               n--;
            }
            return printNumber(n, a);
    }  
}
\$\endgroup\$
0
\$\begingroup\$

At least in teaching, recursion is usually not combined with modifying variables. Therefore the code should look like this:

static void printTriangle(int num, int countdown) {
    if (num > 0) {
        System.out.print(countdown);
        if (countdown > 1) {
            printTriangle(num, countdown - 1);
        } else {
            System.out.println();
            printTriangle(num - 1, num - 1);
        }
    }
}

As you can see, the parameters to the method are never modified. This helps in analyzing and understanding the code. At each point of the execution, you can set a breakpoint and have the full information about all variables.

Compared to your code, I swapped the parameters so that the "more stable" one comes first. This has two reasons:

  • The program is effectively counting down a large number consisting of two "digits". When counting in the decimal system, the digit to the right changes more often than the digit to the left. In your case 55, 54, 53, 52, 51, 44, 43, 42, and so on. It's the same with the two parameters here.
  • When someone asks you "At which point is your program currently?", you would probably say "It's printing the line starting with 4, and in that line it counting down at 2." The order of parameters reflects this.
\$\endgroup\$
3
\$\begingroup\$

Your code is pretty well written, however as always there are things we can change, and other things that are good that I would like to point out.

Positives:

  • You used a method. Dividing and conquering(although it seems small) is very important for shortening and simplifying code. It also prevents bugs.
  • Your code is easy to read

Things to fix:

  • It isn't good to give variables meaningless names. give them names like line rather than a, or num rather than n.
  • You indented 8 spaces after your printNumber method, rather than the usual suggested(and advised) 4 spaces.
  • Instead of doing return printNumber(n, a), simply call the method again, using printNumber(n, a). This makes the program just loop within that method.

If I were just to clean up your code and shorten it when applicable it would look like this:

public class JavaApplication2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int highestNum = scan.nextInt();        
        countDown(highestNum);
        scan.close();
    }

    static int countDown(int highNum) {
        int length = highNum;
        if(length != 0) {   
            for(int i = length; i > 0; i--) {
                System.out.print(i);
            }
            System.out.println();
            highNum--;
            countDown(highNum);
        }
        return 0;
    }  
}

Main changes to your code:

  1. Made your main part the if, rather than the else. This removed the need for an else completely. It keeps looping until line is 0.

  2. Simplified and shortened(a lot).

  3. Changed names of method and variables.


There are many other simple ways to get the same output. Here's a very simple one using a for loop:

public class JavaApplication2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();        
        countDown(num);
        scan.close();
    }
    static int countDown(int num) {
        for(int i = num; i > 0; i--){
            System.out.print(i);
        }
        num--;
        System.out.println();
        if(num != 0) {
            countDown(num);
        }
        return 0;
    }  
}

This program prints the countdown until it is 0, then it starts a new line, decreases num by one, and repeats.


Here's another way just using a double for loop and no recursion.

public class JavaApplication2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int num = scan.nextInt();        
        countDown(num);
        scan.close();
    }

    static void countDown(int num) {
        for(int height = num; height > 0; height--){
            for(int index = height; index > 0; index--) {
                System.out.print(index);
            }
            System.out.println();
        }
    }
}

This one prints index until it is 0 num times, decreasing every time.


The only reason I posted the other possibilities here is really just to prove no. there is no "most optimized" way of achieving this output. That's the beauty of programming, really. You can do the same thing 100,000 different ways. You can make this program using recursion, for-loops, and many other ways too, but they will all give the same output. The goal is to shoot for the cleanest, shortest, and most readable code. If you have any questions, please comment below.

\$\endgroup\$
  • \$\begingroup\$ thanks for the suggestion. its really good and yes, I can achieve it with many different ways but as I mentioned in my question that I want to do it with recursion and I have a feeling that still my recursion is not the most optimize like you have change some part of it :) Anyways I will work on your suggestions they are very good. \$\endgroup\$ – Furqan Jun 28 '17 at 5:20
  • \$\begingroup\$ @Furqan my 1st example uses recursion if that is helpful to you, and thank you for your feedback. I also added a revised version of your method(That was the first block of code). \$\endgroup\$ – CodingNinja Jun 28 '17 at 5:42
  • \$\begingroup\$ Yes, I have seen it and found it very useful. I am looking for more suggestions from others may be it can be optimised further. \$\endgroup\$ – Furqan Jun 28 '17 at 8:29
  • \$\begingroup\$ @Furqan hey there Furqan. I know you wanted a shorter example, so I have shortened my code and optimized it further. Is it acceptable now? Thanks! \$\endgroup\$ – CodingNinja Jul 7 '17 at 2:42
  • \$\begingroup\$ Why the down-vote? Are we not supposed to help people anymore? \$\endgroup\$ – CodingNinja Jul 7 '17 at 16:14
1
\$\begingroup\$

Consider

    static public void displayTriangle(int size) {
        if (size <= 0) {
            return;
        }

        System.out.println(toLineString(size));

        size--;
        displayTriangle(size);
    }

    static public String toLineString(int size) {
        return buildLine(size, new StringBuilder(size)).toString();
    }

    static private StringBuilder buildLine(int size, StringBuilder line) {
        return (size > 0) ? buildLine(size - 1, line.append(size)) : line;
    }

This changes the method signature. You weren't using the return value, so I made this a void method.

We're not printing a number but a triangle. So I changed the name to displayTriangle.

I made the parameter size, which is more descriptive to me.

The original method does two things in the same recursive method. This is confusing. So I changed it to two recursive methods. This helps because part of the complexity of the original was figuring out whether it was printing a line or a triangle. This replaces one complex method with three simple methods.

In my opinion, callers shouldn't have to know internals of how the method works. So my inner recursive method gets a helper method and becomes private. The caller only knows the size that it needs and that it expects a String back. The internal detail of the StringBuilder is hidden from the caller. Want to use a StringBuffer instead? Go ahead. The caller will never know.

I prefer to always use the block form of control structures. This helps avoid certain types of future bugs and is clearer about what is happening. Beyond that, your if and else switched between the statement and block forms in the same structure. That's especially confusing.

If we are returning, we don't need an else. We just return. Everything after the if will be in an implicit else.

Notice how in both cases we can think of the recursion as handling one part of the problem and then recursing with a smaller sized problem.

It is more efficient to call println once on the whole line than to keep calling print with just one character. And of course to build the whole line, we use a StringBuilder.

\$\endgroup\$
  • \$\begingroup\$ thanks for the explanation and for the code ... I really like the solution but I guess the below one is more optimized thats why I am accepting that one. \$\endgroup\$ – Furqan Jul 12 '17 at 3:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.