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.