I was watching a video about a mathematical concept in which someone tried to explain how to rewrite a recursive function into something that could be written in a programming language that couldn’t do recursion – but still ended up writing recursive functions which were supposedly impossible.

Rewriting recursion into something that isn’t recursive is actually really useful in programming, as recursion usually fills up your stack rapidly with information that you usually don’t really need to actually run the code.

So here’s an example of Actually rewriting a functional and recursive piece of code to something that doesn’t use recursion.

The same as with the video I watched, I will try to do this with the function to calculate the factorial of a number.

**n!**

n! or n factorial is a simple little function that calculates 1 * 2 * 3 * 4 … * n, so for example 6! = 1*2*3*4*5*6 = 720

**Introduction to functional code**

To go about writing a functional implementation for n!, it’s important to know that the function works based on conditions. Namely that n usually has to be a natural and positive integers, and that 0! is always 1 despite the previous explanation.

In functional languages you usually write down the conditions as overloaded versions of the actual function, like this:

fac(0) => 1

fac(n) => n * fac(n-1)

We write this down as going from n down to 0, because we can’t really check and stop counting things up in functional languages (*we would need a global variable that introduces side effects*), luckily for factorial the order in which you multiply the numbers doesn’t matter.

To do 1 less recursion, you could write 1 more condition:

fac(0) => 1

fac(1) => 1

fac(n) => n * fac(n-1)

**Transforming functional into procedural**

Sometimes we can just copy paste functional code into regular programming languages without any problems, but considering we can’t really overload functions based on content – only on types of parameters or number of parameters – we need to rewrite this first.

We can do this simply by writing the conditions as part of the base function and returning the desired conditional function, in this case, if the input is 0 => we simply return 1 instead of n * fac(n-1).

function fac(int n)

if (n==0) return 1;

return n * fac(n-1);

**) assuming n >= 0, or things will get out of hand*

**Transforming recursion into loops**

Recursion takes up a lot of memory, the higher input n gets, the more memory and CPU time the program will demand – perhaps even crashing with the infamous error “Stack overflow”.

So whenever we feel like we might run into these kinds of problems, we can rewrite our code into looping code.

We can rewrite this code in a lot of ways, but let’s try this as if we’re really uncreative.

To do this – in a rather complicated way – we need to do the following:

- Use a result variable
- Replace the recursion point to using a variable that remembers the input for each iteration
- Loop until the needed conditions are met

function fac(int n)

if (n == 0) return 1;

if (n == 1) return 1;

int result = n;

int nextn = n;

while trueif (nextn == 0) return result;

if (nextn == 1) return result;

result = result * (nextn – 1);

nextn–;

Note that we’re using the shortcutting version with an extra condition for when nextn is 1, not because we fancy that, but because we have to prevent multiplying by 0. Of course, we could write these two if statements as one because they leave us with the same result. So something like if (nextn <= 1) return result;.

To have a slightly cleaner version, instead of having a certain 0 condition everywhere, we can write the 0 condition result as the initial result and not decrement nextn twice. In this version we also don’t need the 1 condition, because the function always returns before it can multiply by 0.

function fac(int n)

int result = 1;

int nextn = n;

while trueif (nextn == 0) return result;

result = result * nextn;

nextn–;

And of course, instead of using an infinite loop, we can embed the stop condition into the loop definition by checking if the opposite is true.

function fac(int n)

int result = 1;

int nextn = n;

while (nextn <> 0)result = result * nextn;

nextn–;return result;

## Why did we do this again?

As usual with these kinds of rewrites and optimizations, we have to do a lot of thinking to get things done. By now the function looks nothing like we initially started with, and perhaps we were better off doing this the “normal” way instead of this functional nonsense. Whenever you see something counting; write a for-loop.

function fac(int n)

int result = 1;

for (int nextn = n; nextn > 1; nextn–)result = result * nextn;

return result;

But why do it the easy way when we can apply really slow and impractical concepts from functional languages 😉