Tutorial: Pascal's Triangle - Manhunter07/MFL GitHub Wiki

Pascal's Triangle is one of the most significant number sequences in all of math. Among other things, it defines the binominal coefficients, used as exponents for the binominal formulas. In this tutorial, we will build a function that determines the n'th sequence of the Pascal's Triangle using recursion.

Concept

In theory, Pascal's Triangle can be described with the formula:

(n + 1, k + 1) = (n, k) + (n, k + 1)

n stands for the current row and k for the current column, both starting at 0. Because it's an equiangular triangle, the maximum possible n always equals the current value of k. The first few rows look as follow:

  • 1
  • 1, 1
  • 1, 2, 1
  • 1, 3, 3, 1
  • ...

Implementation

Function design

We can declare a function to implement a Pascal's Triangle. The header could look as follow, using PosInt as the type for n (the bottom row index).

function PascalsTriangle(N: PosInt): array

The function would call itself recursively for any n > 0 and return a constant [1] for n = 0. As result we would return a 2-dimensional array of numbers, the first dimension (primary index) to represent a row and the second dimension (secondary index) a column:

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], ...]

Access to a specific value could therefore be represented by the following function:

function GetPascalsTriangleAt(n & k: PosInt) = PascalsTriangle(n).(n).(k)

Function code

The function has two different implementations:

  • For n = 0 it returns [1]
  • For n ≠ 0 it returns the processed result of n - 1 with an appended 1-element

For simplicity, we leave out the parameter and return types here.

function PascalsTriangle(n) = if n ?= 0 then [1] else [1] + Creep(PascalsTriangle(n - 1), 2, Add) + [1]

The way this functions works is, it makes use of the Creep function to sum each pair of numbers, thus temporarily reducing the column count by one. Afterwards, it prepends and appends [1] each, increasing the result length by two. We therefore end up with an additional numeric element and a modified value chain, dependent on the previous iteration. Dependent on the input parameter n, the function calls itself n - 1 times.