recursion - Are recursive functions used in R?

Question

The canonical function to demonstrate recursion is the factorial() function. I tried a simple implementation of it myself and came up with this:

factorial <- function(x){

if(x==1)
    return( 1)
else
    return(x*factorial(x-1))

}

From my survey of the topic, there seems to be some debate about whether it's better to use recursion or simple iteration. I wanted to see how R implements it and found a factorial() function in the gregmisc package. I thought I'd find something like my implementation or instead a regular iteration. What I found this:

> factorial
function (x) 
gamma(x + 1)
<environment: namespace:base>

So the answer to my question of whether R prefers recursion or iteration is "neither". At least in this implementation. Are recursive functions avoided in R for good reason?

Update:

gregmisc version:

>ptm <- proc.time()
> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
   user  system elapsed 
  0.001   0.000   0.001 

my version:

> factorial(144)
[1] 5.550294e+249
> proc.time() - ptm
  user  system elapsed 
  0.002   0.001   0.006 

Answer 1

For calculation of integer factorial, the recursive implementation is slower and more complex. Invariably, iteration is used in production code.

The factorial function you refer to is in the base package. It operates on real values rather than integers, hence that implementation. Its documentation states:

factorial(x) (x! for non-negative integer x) is defined to be gamma(x+1)

A more interesting example is code to implement the Fibonnaci series which is extraordinarily wasteful when implemented with a naive recursion. The recursive approach can be made efficient through memoization but simple iteration is always to be preferred if performance is at stake.

Another common algorithm that is expressed naturally in a recursive way is Quicksort. This can, like all algorithms be implemented without recursion, but is quite complex to do so. There is little benefit in using a non-recursive Quicksort and so it's common to use the naive recursive implementation.

Recursion is a good implementation choice:

• if performance is not compromised, and
• if it is more natural (hence easier to verify and maintain) to implement recursively.