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

```
def exp(_x, 0) do
1
end
def exp(x, n) when n > 0 do
(:math.pow(x,n) / fac(n)) + exp(x, n-1)
end
def fac(0) do
1
end
def fac(n) when n > 0 do
n * fac(n-1)
end
## read from stdin and return a list of integers
def read(line \\ []) do
case IO.read(:stdio, :line) do
:eof ->
{:eof, line}
{:error, reason} -> IO.puts "Error: #{reason}"
data ->
item = String.to_float(String.trim(data))
line = line ++ [item]
read(line)
end
end
end
# read n
_ = IO.gets(:stdio, "")
|> String.trim("\n")
|> String.to_integer
# read a list of integers
{:eof, l} = Solution.read()
Enum.each(l, fn x -> IO.puts "#{Solution.exp(x, 9)}" end)
```

The same program written in python looks as follows:

```
import math
def fac(n):
if n == 0:
return 1
else:
return n * fac(n - 1)
def exp(x,n):
if n == 0:
return 1.0
else:
return float(math.pow(x,n))/float(fac(n)) + exp(x, n-1)
print(exp(1.0,100))
```

Our python program declares two functions `fac(n)`

and `exp(x,n)`

. Both of these functions are defined recursively, but this time rather than two separate functions like we see with elixir, we have the base-case of our function captured in an `if-then-else`

clause. The `if-clause`

implements the base-case, and the `else-clause`

is our recursive definition.