4
\$\begingroup\$

This is a fully functional implementation of a program to ask the user for a location on Pascal's Triangle, but I kind of cheated by expanding the base case to include row 0 and the 1st and last columns. I feel like this isn't a great approach, but I'm not quite sure why. (Note: I'm not a complete beginner, but I'm definitely not an experienced programmer by any definition)

import java.util.Scanner;
public class Pascal {
    public static void main(String[] args) {
        int r, c;
        Scanner sc = new Scanner(System.in);
        System.out.println("Row #");
        r = sc.nextInt();
        while (r != -1)
        {
        System.out.println("Column #:");
        c = sc.nextInt();
        System.out.println("\n" + calcPascal(r, c));
        //Just here for the while loop
        System.out.println("\nRow #");
        r = sc.nextInt();
        }
    }

    public static int calcPascal(int row, int column)
    {
        int pasVal;
        if (column == 0 || column == row || row == 0) 
        //
        {
            pasVal = 1;
        }
        else
        {
            pasVal = calcPascal(row - 1, column - 1) + calcPascal(row - 1, 
            column);
        }       
        return pasVal;
    }
}
\$\endgroup\$
1
\$\begingroup\$

Thanks for sharing your code.

Comments

Your code has (essentially) only one comment.

Comments should explain why the code is like it is. Your (first) comment is a good example.

Naming

Finding good names is the hardest part in programming, so always take your time to think about the names of your identifiers.

Please read (and follow) the Java Naming Conventions. The name of your base class starts with a lower case letter which should be upper case instead.

Avoid Single Character Names and Abbreviations

Since the number of characters is quite limited in most languages you will soon run out of names. This means that you either have to choose another character which is not so obviously connected to the purpose of the variable or you will have to "reuse" variable names for different, possibly unrelated contexts. This makes your code hard to read and understand for other people (keep in mind that you are that other person too, if you look at your code in a few months!) The same is true for abbreviations. You might find them obvious today, while you're actively dealing with the problem, but you might have to "relearn" them if you worked on something else for a while.

On the other hand, Java's identifier names can be virtually unlimited in length. There is no penalty in any way for long identifier names. So don't be stingy with letters when choosing names.

Define Variables as Late as Possible

You define your variables at the beginning of main. But the variable c is used only within the loop. This makes it hard to move the coin drop code to its own method. Your IDE's automated refactoring will introduce both an extra parameter and an unneeded return value. So always declare variables just before their first use unless they are magic numbers.

Magic Numbers

Your code has some magic numbers. They are literal values with a special meaning like here:

while (r != -1)
//...
    if (column == 0 || column == row || row == 0) {
        pasVal = 1;

You should introduce constants with meaningful names:

public static final int LOWEST_INDEX = 0;
public static final int TRIANGLE_START_NUMBER = 1;
public static final int INVALID_INDEX = -1;
// ...

while (r != INDEX)
//...
    if (column == LOWEST_INDEX || column == row || row == LOWEST_INDEX){
        pasVal = TRIANGLE_START_NUMBER;
\$\endgroup\$
  • 1
    \$\begingroup\$ While I appreciate your answer, and you raise several good points, I was taught that creating your variables mid-program is not a good idea, especially in a short code like this one. There are actually more comments in the original code; the reason I did not copy them all is because it is very obvious from the question what this code is doing. The reason for R and C instead of row and column is because I did not want to overload the variables here, though I concede there are better ways to handle it. \$\endgroup\$ – nathaniel sokolow Nov 12 '17 at 14:22
1
\$\begingroup\$

Welcome to Code Review! I would suggest some structural changes to your program, first, before discussing the algorithm.

In your main program, you scan for input of the row once before the loop and once inside the loop after calcPascal(r,c). You can rearrange the code in the following way to write the scan only once and to also check for stronger boundary conditions. If the user types any negative number, the program should exit so we need to check against that as well. Also, the names can be row and column, they will not overload those in the calcPascal function. Here's my suggestion for main:

int row, column;
boolean should_exit = false;
Scanner input = new Scanner(System.in);
while (!should_exit) {
    System.out.print("Row: ")
    row = input.nextInt();
    if (row >= 0) {
        System.out.print("\nColumn: ");
        column = input.nextInt();
        if (column >= 0) {
            System.out.println("\n" + calcPascal(row, column);
            continue;
        } 
    }
    should_exit = true;
}

Now for your algorithm. The Pascal triangle is an inherently recursive structure, and therefore it would not be unreasonable to write a recursive method to calculate its values. This works for small values of row and column but it will most likely lead to a stack overflow for large values. If you want to stick to a recursive function, the best thing you can do is remove the variables all together and try and get the function into a "tail-recursive form" by which we mean that the function itself is returned as the last statement. Here's what I mean:

public static int calcPascal(int row, int column) {
    if (row == column || row == 0 || column == 0)
        return 1;
    else 
        return calcPascal(row - 1, column - 1) + calcPascal(row - 1, column);
}

This will improve readability and speed of your code as Java will optimize the call to the calcPascal.

(Also note that there is nothing wrong with making your base case zero, all this does is zero index the triangle. If you want to make it start at one, then you will need to change the base case to check against one and the loop in main will have to check against one also. I suggest leaving it like it is, it's actually more mathematically correct.)

The other alternative to the recursive algorithm is to use an iterative method by use of combinations. The row and column of Pascal's triangle are the Binomial Coefficients where row=n and column=k. Using the equation for finding the binomial coefficients will be faster than a recursive method for large values of row and column.

\$\endgroup\$

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.