Tutorial: Constructing Pascal's triangle

Pascal's triangle is made up of several rows of numbers, with each successive row having one more number than the previous row. When the rows are stacked, a triangle-like pattern is formed, hence its name. Each element is the sum of the two elements on top of it. The first element (at the tip) is 1. At the sides, where there is only one element, it will be the equal to the sum of the element above it and zero -- 1.

1
11
121
1331
14641
...

The rows of Pascal's triangle can be constructed recursively. Recursion is said to occur when a function calls itself repeatedly until the problem is reduced to a base problem for which the answer is defined. Notice that each row of Pascal's triangle can be derived solely from the previous row. To get the nth row, we must already have the (n-1)th row. Proceeding in this manner, eventually we must ask: What is the first row? This is thus the base problem.

Let's start with some VB code (the questions come later):

01: Function p(n)
02: If (n = 1) Then
03: p = 1
04: Exit Function
05: End If
06: p = p(n - 1)
07: For i = n To 2 Step -1
08: If (i > Len(p)) Then
09: p = p & Right(p, 1)
10: Else
11: Mid(p, i, 1) = CInt(Mid(p, i, 1)) + CInt(Mid(p, i - 1, 1))
12: End If
13: Next
14:End Function

We call the function p(n) to get the nth row of Pascal's triangle. The first if clause is basically the solution to the base problem. The next line tells the function to call itself again, this time solving for the previous row. The for clause describes how to get the next row from the previous row and deserves a little more attention.

Consider the third row of Pascal's triangle (121). How would we morph this into the fourth row? We start from the right end of the row. The fourth row should have four elements, so first let us append the last element (1 + 0, see introductory remarks; it is also okay to directly append a 1). We are now done with the 4th element; the row now says 1211.

Now proceed to the 3rd element. In the fourth row, the 3rd element is the sum of the second and third element from the third row (2 + 1). The element is then updated (1231). Similarly, the 2nd element is updated (1331). The first element does not require any change (0 + 1), so we can leave it as it is (final result: 1331).

Back to the for clause: The index i is used to track which element of the row is being changed. The initial value of i is n, and Step -1 tells it to reduce i by 1 at the end of every iteration. The first part of the if clause appends the last element (Mid function would return a zero-length string because n > Len(p)). The second part updates the remaining elements in the row, as described. CInt converts the output of Mid to an integer so that the + operator adds them up instead of concatenating the two strings.

To verify that the row is constructed correctly, calling MsgBox p(5) gives 14641, as expected.

Discussion questions:
1. What are the potential problems with this VB function? Try calling p(6); are the results as expected? Why?
2. The elements of the triangle can grow quickly. How would you quickfix the above code to cater for larger numbers, say p(10)?
3. Is the VB language suitable for this purpose?
4. Note that the function merely provides a particular row of the triangle, whereas the title says "Constructing Pascal's Triangle". Would you use this function to construct Pascal's triangle? Why? (In particular, is it efficient?)
5. How would you modify the function to actually construct Pascal's triangle?