Pascal's triangle - Recursion

Question

Problem:

Pascal’s triangle is a useful recursive definition that tells us the coefficients in the expansion of the polynomial (x + a)^n. Each element in the triangle has a coordinate, given by the row it is on and its position in the row (which you could call its column). Every number in Pascal’s triangle is defined as the sum of the item above it and the item that is directly to the upper left of it. If there is a position that does not have an entry, we treat it as if we had a 0 there. Below are the first few rows of the triangle:

Item: 0 1 2 3 4 5

Row 0: 1

Row 1: 1 1

Row 2: 1 2 1

Row 3: 1 3 3 1

Row 4: 1 4 6 4 1

Row 5: 1 5 10 10 5 1

 `...`

Define the procedure pascal(row, column) which takes a row and a column, and finds the value at that position in the triangle. Don’t use the closed-form solution, if you know it. def pascal(row, column)

Solution:

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5, 4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 elif row == 0:
 return 0
 else:
 return pascal(row-1, column) + pascal(row-1, column-1)

Can we improve this code using memoization? because, pascal(5,4) = pascal (4, 4) + pascal(4, 3)

• VictorHMartin: I think this algorithm is wrong, as pascal(4, 2) will return 7 instead of 6, for example.

Answer 1

Rather than memoizing the applicable portion of Pascal's triangle, you could calculate the value much faster either along the row or along the diagonal.

Let \$n\$ represent the row and \$k\$ represent the column. We know that \$\tbinom{n}{0}=1\$ and \$\tbinom{1}{k} = k\$. To compute the diagonal containing the elements \$\tbinom{n}{0}\,ドル \$\tbinom{n+1}{1}\,ドル \$\tbinom{n+2}{2}\,ドル \$...\,ドル we can use the formula

$$ {n+k\choose k}= {n+k-1\choose k-1}\times \frac{n+k}{k}, ~ k > 0. $$

To calculate the diagonal ending at \$\tbinom{7}{2}\,ドル the fractions are \$\tfrac{6}{1}\,ドル \$\tfrac{7}{2}\,ドル and the elements are

$$ \begin{align*} \tbinom{5}{0}&=1,\\ \tbinom{6}{1}&=\tbinom{5}{0}\times\tfrac{6}{1}=1\times\tfrac{6}{1}=6,\\ \tbinom{7}{2}&=\tbinom{6}{1}\times\tfrac{7}{2}=6\times\tfrac{7}{2}=21.\\ \end{align*} $$

Looking up on the table to verify, \$pascal(7,2) = 21\$.

Applying this,

def pascal(row, column):
 """
 >>> pascal(0, 0)
 1
 >>> pascal(5, 4)
 5
 >>> pascal(0, 1)
 0
 """
 if column == 0:
 return 1
 if row == 0:
 return column
 return (row * pascal(row-1, column-1)) / column

Other things you may want to consider are recognizing that there are bounds. column and row must be positive and column is bounded to row+1.

Indexing tricks on the column value could be employed to reduce the amount of calculations on the diagonal.

When a control structure interrupts the flow of a program like return does in your program, do not use elif or else. This helps with readability (less of the control path to keep track of and reduces indentation on else) and improves maintainability. Semantically both are equivalent, but in larger codebases, multiple control paths become a pain.

• Janne Karila: +1, though I might argue that the else improves readability because you can see that there are mutually exclusive blocks of code without reading the blocks themselves.
• KingMongolian: if row == 0: return 1 ^^ Doesn't return column return 0, which makes the other value 0.