You will start by learning how to construct Pascal’s triangle. You’ll then proceed to write a Python function and learn to optimize it further. ▶️ Let’s begin!
What is Pascal’s Triangle & How to Construct it?
Printing Pascal’s triangle for a given number of rows is a popular interview question. So the first row has one element, and it’s 1. And each element in subsequent rows is the sum of the two numbers directly above it. The following figure explains how to construct Pascal’s triangle with five rows. Notice how you can pad zeros when you have only one number above a certain number. 📝As a quick exercise, follow the procedure above to construct Pascal’s triangle for n = 6 and n = 7. Next, let’s proceed to write some code. You may choose to run the code snippets on Geekflare’s Python IDE right from your browser— as you work your way through the tutorial.
Python Function to Print Pascal’s Triangle
In this section, let’s write a Python function to print Pascal’s triangle for any given number of rows. There are two key questions to consider:
How to express the entries in Pascal’s triangle?How to print Pascal’s triangle with appropriate spacing and formatting?
Let’s answer them now. #1. What’s the expression for each entry in Pascal’s triangle? It so happens that the entries in Pascal’s triangle can be obtained using the formula for nCr. If you recall from your school math, nCr denotes the number of ways you can choose r items from a set of n items. The formula for nCr is given below: Now let’s proceed to express the entries in Pascal’s triangle using the nCr formula. We’ve now found a way to express the entries in the matrix. #2. How to adjust spacing when printing the pattern? In Pascal’s triangle with numRows, row #1 has one entry, row #2 has two entries, and so on. To print the pattern as a triangle, you’ll need numRows - i spaces in row #i. And you can use Python’s range function in conjunction with for loop to do this. Now that you’ve learned how to represent entries and also to adjust space while printing Pascal’s triangle, let’s go ahead and define the function pascal_tri.
Parsing the Function Definition
So what do you want the function pascal_tri to do?
The function pascal_tri should accept the number of rows (numRows) as the argument.It should print Pascal’s triangle with numRows.
In order to compute the factorial, let’s use factorial function from Python’s built-in math module. ▶️ Run the following code cell to import factorial and use it in your current module. The code snippet below contains the function definition. The function works as follows:
The function pascal_tri has one required parameter numRows: the number of rows.There are numRows rows in all. For every row i, we add numRows - i leading spaces before the first entry in the row.We then use nCr formula to compute the individual entries. For row i, the entries are iCj where j = {0,1,2,..,i}.Observe that we use // which performs integer division, as we’d like the entries to be integers.After computing all entries in a row, print the next row in a new line.
🔗 As we’ve added a docstring, you can use Python’s built-in help function, or the doc attribute to access the function’s docstring. The code snippet below shows how to do it. Now let’s go ahead and call the function with the number of rows as the argument. The first 3 rows of Pascal’s triangle are printed, as expected.
Print Pascal’s Triangle Using Recursion
In the previous section, we identified the mathematical expression of each entry in the Pascal Triangle. However, we did not utilize the relationship between entries in two consecutive rows. In fact, we used the previous row to compute the entries in the subsequent row. Can we not use this and come up with a recursive implementation of the function pascal_tri? Yes, let’s do that! So the function call to pascal_tri(numRows) in turn calls pascal_tri(numRows-1) and so on, until the base case pascal_tri(1) is reached. Consider the example where you need to print the first 3 rows of Pascal’s triangle. The following image explains how the recursive calls are pushed to the stack. And how the recursive function calls return the rows of Pascal’s triangle. ▶️ Run the code snippet below to generate the rows of Pascal’s triangle recursively. Here are a few points worth making note of:
We’ve used a nested list as the data structure, where each row in Pascal’s triangle is a list in itself, like this: [[row 1], [row 2],…,[row n]].The function call pascal_tri(numRows) triggers a series of recursive calls with numRows - 1, numRows - 2 all the way up to 1 as the arguments. These calls are pushed onto a stack.When numRows == 1, we’ve reached the base case, and the function returns [[1]].Now the returned list is used by the subsequent functions in the call stack—to compute the next row. If cur_row is the current row, cur_row[i] = prev_row[i] + prev_row[i+1]—the sum of 2 elements directly above the current index.
As the returned array is a nested list (list of lists), we need to adjust spacing and print out the entries, as shown in the code cell below. The output is correct, as seen below!
Python Function to Print Pascal’s Triangle for numRows ≤ 5
Both of the methods that you’ve learned will work to print Pascal’s triangle for an arbitrary number of rows numRows. However, there are times when you need to print Pascal’s triangle for a smaller number of rows. And when the number of rows you need to print is at most 5—you can use a straightforward technique. Go through the figure below. And observe how the powers of 11 are identical to the entries in Pascal’s triangle. Also, notice that this works only up to the 4th power of 11. That is, 11 raised to the powers {0, 1, 2, 3, 4} gives the entries in rows 1 through 5 of Pascal’s triangle. Let’s rewrite the function definition, as shown below: Here’s how the function pascal_tri works:
As with the previous examples, we adjust the spacing.And then, we use Python’s exponentiation operator (**) to compute the powers of 11.As the powers of 11 are integers by default, convert them to a string using str(). You now have the powers of 11 as strings.Strings in Python are iterables—so you can loop through them and access one character at a time.Next, you may use the join() method with the syntax:
Let’s check if the function works as intended. As another example, call the function pascal_tri with 4 as the argument. I hope you know understand how you can easily print the Pascal triangle for numRows in the range 1 to 5.
Conclusion
Here’s what we’ve learned:
How to construct Pascal’s triangle with the given number of rows. Every number in each row is the sum of the two numbers directly above it.Write a Python function using the formula nCr = n!/(n-r)!.r! to compute the entries of Pascal’s triangle.You then learned a recursive implementation of the function.Finally, you learned the most optimal method to construct Pascal’s triangle for numRows up to 5—using the powers of 11.
If you’re looking to level up Python skills, learn to multiply matrices, check if a number is prime, and solve problems on string operations. Happy coding!
