Brew up some Elixir recursion

Recursion is recursion is recursion is recursion….

So how hard is it to go back to a programming language that you haven’t used for months that you only used for less than a year? Well, it took me a few more minutes than I anticipated, but in the end, I was succesful!

Tonight, I thought I’d take the simple idea of creating Pascal’s Triangle. A simple construction that creates a table of binomial coefficients for the binomial $(x+y)^n = x^4+4x^3y+6x^2y^2+4xy^3+y^4$. Notice the coefficients in our expanded binomial:

$$1, 4, 6, 4, 1$$

These numbers correspond to the 5th line of our triangle (See the pretty picture above). How do we calculate the lines in the triangle? Well, using combinatorics, we can use the following combination:

$\dbinom{n}{k}$, where $n\ge{k}\ge0$.

But what if we wanted to compute the coefficients recusively? Looking at the diagram, we quickly see that the following is true:

• the beginning of a row is always 1, $k=0$
• the end of a row is always 1, $k=n$
• otherwise, each interior row element equals the sum of the row directly above, and the column to the left, added to the row directly above at the same column position of the row as the one being calculated.

We can rewrite that wordy sentence above into a recurrence relation:

line(column, row) -> 1 when column is zero

line(column, row) -> 1 when column equals row

for all others line(column, row) -> line(column -1 , row - 1) + line (column, row -1)

So, now that we see how to define the base case and the recurrence relation, let’s write some code. But instead of writing in a procedural language like Python, let’s give it a go in a Functional language like Elixir!

defmodule Pascal do

        def line(col, row) do
                cond do
                        col == 0 -> 1
                        col == row -> 1
                        true -> line(col - 1, row - 1) + line(col, row - 1)
                end

        end

        def tree(n) when n > 0 do
                Enum.reduce(0.. n,[1], fn(r, ra) -> ra ++
                        [Enum.reduce(0..r, [], fn(c,ca) ->
                                ca ++ [Pascal.line(c, r)]
                        end)]
                end)
        end

        def print(tree_list) do
                Enum.reduce(tree_list, fn(t, _) ->
                        IO.puts "#{inspect t}"
                end)
        end

end

A quick look at the code reveals three functions: line/2, tree/1, and print/1 all defined in our Pascal module.

The first function, line is our recursive function. To be fair, I didn’t write this idiomatically. In Elixir, a more idiomatic way of writing it would have been to write multiple signature functions for line. But I wanted to make the example as straight-forward as possible for the noob looking at elixir for the very first time.

The tree/1 function takes a single parameter, n, and constructs a tree of lists of height n+1.

Lastly, we define print/1 that takes our list and prints it out for all to see.

Running our program in iex we see the following output when we call our function for a height of $n=5$:

Pascal.print(Pascal.tree(5))
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

And there you have it! A recursively defined function in Elixir that creates Pascal’s Triangle!

For those interested in the idiomatic solution, I included it below:

defmodule Pascal do

        def line(0, _), do: 1
        def line(col, row) when col == row, do: 1
        def line(col, row) do
                line(col - 1, row - 1) + line(col, row - 1)
        end

        def tree(n) when n > 0 do
                Enum.reduce(0.. n,[1], fn(r, ra) -> ra ++
                        [Enum.reduce(0..r, [], fn(c,ca) ->
                                ca ++ [Pascal.line(c, r)]
                        end)]
                end)
        end

        def print(tree_list) do
                Enum.reduce(tree_list, fn(t, _) ->
                        IO.puts "#{inspect t}"
                end)
        end

end