Recursion Revisited

Recursion, from more than one point-of-view.

A common programming idiom in computer science is solving a problem by self-reference, also known as recursion. In this post, we look at two different implementations of the same problem.

Solve a recursive problem in two different programming language paradigms

Let’s look at the solution to a simple problem, compute $f(x)=e^{x}$.

We will illustrate two separate solutions - one in a procedural language (python), and the other in a functional language (elixir).

Let’s start off with the functional language. Were does recursion come into play?

We define the function $f(x)=e^x$ as the infinite sum, $\text{ }f(x) = \sum_{n=0}^\infty{\frac{x^n}{n!}}$

In our solution below, we define two separate recursive functions, exp/2 and fac/1. What’s interesting to note here is how each of these functions has two separate definitions. This is an aspect of programming in elixir that elegantly uses pattern-matching to return different results depending upon the input. Our two functions nicely dovetail into the base-case and recursive case of a recursive algorithm.

For example, looking at exp/2, the first function definition returns 1 for any value of x (as indicated by the _ preceding the variable) and returns 1. This is the mathematical equivalent of $x^0=1\text{ for any }x$.

The second definition of exp/2 is the recursive case. for any value of $n\gt0$. Moreover, we define exp(x, n) as $\frac{e^x}{n!}$ + exp(x, n-1).

Similarly for the definition of fac/1 we see two definitions; one for $n=0$ and another for all values of $n\gt0$.

Continue reading

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$. Continue reading

Visualizing the News: Grab your PILlow

A Picture’s Worth a Gazillion Bits newsapi This weekend, I tripped over a neat news REST-ful api called newsapi. Grab an API key and you’re off to the races. There are tons of live headlines - News API can provide headlines from 70 worldwide sources. There are basically two api endpoints: GET https://newsapi.org/v1/articles GET https://newsapi.org/v1/sources Register for an account and generate an api-key and let’s get started. Accessing the API with Python newsapi can easily be accessed using a browser since the REST-ful method used is a GET method. Continue reading

Making Heads or Tails out of Recursion and Combinatorial Math

GNU — GNU’s Not Unix I thought I’d take a look at two topics at once and make some fun by mashing them together. Today’s topic is recursion. In computer science (and in math, although we call the equation a recurrence relation) recursion is an often misunderstood concept causing lots of panic and anxiety. In reality - it’s pretty easy once you wrap you head around the idiom. What is recursion? Continue reading