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