### CyberSpy

Rantings from a guy with way too much free time

# Recursion Revisited

2017-11-28

### 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$.

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