### CyberSpy

Rantings from a guy with way too much free time

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

  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
:eof ->
{:eof, line}

{:error, reason} -> IO.puts "Error: #{reason}"

data ->
item = String.to_float(String.trim(data))
line = line ++ [item]

end

end

end

_ = IO.gets(:stdio, "")
|> String.trim("\n")
|> String.to_integer

# read a list of integers

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.

### Brew up some Elixir recursion

2017-11-17
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