Let’s say we want to implement the good old factorial function but we do not want to use recursion. Instead we will write an infinite number of custom factorial functions that take just one value:

```
= 1
fact0 = 1 * fact0
fact1 = 2 * fact1
fact2 = 3 * fact2
fact3 = 4 * fact3
fact4
.
. .
```

This will work fine, it is just a little inconvenient since it is, well
infinite. But maybe we can functionalize it by writing a `factR`

that creates a
factorial function with the factorial function for *N* − 1 as an input.

```
<- function(r){
factR function(n){
if (n == 0){
1
else {
} * r(n - 1)
n
}
} }
```

What values do we use for `r`

? We can create the `r`

function with `factR`

:

For !0:

```
R> factR(NULL)(0)
1
```

We pass in a `NULL`

function. If this function is called, then an error will be
raised. But it isn’t called since *n* = 1 and thus 1 is returned. If instead we
input 1:

```
R> factR(NULL)(1)
Error in r(n - 1) : could not find function "r"
```

We need to go deeper.

```
R> factR(factR(NULL))(1)
1
```

What about 2, 3, 4?

```
R> factR(factR(factR(NULL)))(2)
2
R> factR(factR(factR(factR(NULL))))(3)
6
R> factR(factR(factR(factR(factR(NULL)))))(4)
24
```

So long as the `factR`

fnctions are nested deeper than the input `n`

, the
expression evaluates correctly. But writing these deeply nested expressions is
tedious. So let’s write a function to do it for us:

```
<- function(k, f){
kfunctions if(k < 1){
error("k must be greater than or equal to 1")
}= list()
fs for(i in 1:k){
= f
fs[[i]]
}Reduce(function(x, r){r(x)}, fs, NULL)
}
```

There is nothing in `kfunctions`

that is specific to the factorial function, so
we just call the input function `f`

. The only requirement is that `f`

MUST be a
function that takes a function as an argument and returns a new function. Now we
can use `kfunctions(3,factR)`

as a short cut for `factR(factR(factR(NULL)))`

.
For the case of factorial, where it is easy to calculate the required recursive
depth, we could write the factorial solution:

```
<- function(n){
fact kfunctions(n+1, factR)(n)
}
```

This new `fact`

function will work neatly for any number. But what if we don’t
know how deeply we need to recurse? What we need is something like `kfunction`

but that can be infinite. Fortunately, R happens to be lazy, so inifinity plays
nicely.

```
<- function(f){
fix f( fix(f) )
}
```

The function `fix`

encapsulates the notion of recursion. It takes a
non-recursive function and makes it recursive. The important thing to remember
is that the non-recursive function must be a function that takes a function as
an argument and returns a function.

Now we can write our factorial functions as:

`<- fix(factR) fact `

This solution is fully general, it will work for more complex recursive problems, such as calculating the fibonacci sequence which branches recursively:

```
<- function(r) {
fibR function(n) {
if (n == 0){
1
else if (n == 1){
} 1
else {
} r(n-1) + r(n-2)
}
}
}
= fix(fibR) fib
```

The reason `fix`

does not fall into an infinite recursive loop is because of R’s
laziness. `r`

is an infinitely nest of `fibR`

functions, but the thunk `fix(f)`

is not evaluated until its value is needed, thus is remains finite and expands
to `f( fix(f) )`

only when needed. So the evaluation rolls all the way down to
the base cases of 0 and 1 and then wrap back up summing the values.

What is the point of all this? Well, we have factored recursion out of R. Now
all recursive handling can be managed within one function. And we can modify
this function to modify how recursion itself works. We can rewrite the `fix`

function to, for example, memoize intermediate values. And that is just the
beginning. There are many more complex recursive patterns we can abstract from
our code, but this is a topic for a future post.