Programming Outside the Box: A Recursive Function in R

I heard a talk given by Ruby creator Yukihiro Matsumoto where he was rambling about how he came about becoming a programming language developer. He mentioned an important milestone as being his grasp of the idea behind recursion. I’ve kept that in mind and decided to dig into the idea a little bit and was pleased to discover something quite clever.

If you need to loop over some data set, you essentially have two options. Control flow iteration, which uses your common for loops and the like, and recursion. At first blush, recursion is very mysterious. The canonical example is the factorial() function where you multiply an integer by all the integers less than it and stop at 1. You remember from high school:  5! = 5x4x3x2x1.

I’ve written the following R implementation of it below:

factorial <- function(x){
    
    if(x==1)
        return( 1)
    else
        return(x*factorial(x-1))
        
}

If you need to stare at it for a while, you’re not alone. How does a function call itself? Shouldn’t this simply blow up with a laundry list of errors at minimum and at worse a complete crash of your computer?  Well, actually it works. Try it. This is how it flows:

factorial(5)
5*factorial(4)
5*(4*factorial(3))
5*(4*(3*factorial(2)))
5*(4*(3*(2*factorial(1))))
5*(4*(3*(2*1)))
120

I thought to see how R prefers to implement the factorial() function and found my answer in the gregmisc package. This is the code for its factorial() function:

function (x) 
gamma(x + 1)

Okay, so what is the gamma() function? From the R help files, I got this definition:

Γ(x) = integral_0^Inf t^(x-1) exp(-t) dt

At some point I need to have the ability to blog functions in common mathematical notation and add some clarity to a dense concept, but for now that’s all I got. To be honest, if I had to explain the gamma function for 5 minutes, I would fail. At minimum though, I think mine is simpler.

UPDATE: Best wishes to Matz and his native Japan. May damage be minimized and recovery swift.