Statistics 5931 (Geyer, Fall 2003) Recursive Functions

This page is about recursive functions in R, although it really isn't about R. It's about recursive functions in general and only incidentally about R. The same issues arise in any modern programming language. There are some problems that are only done cleanly using recursion.

The problem was posed by Dave Nelson and Glen Meeden. They came into my office one afternoon recently with the following question. Suppose I have a bunch of vectors, say x, y, and z, for example. And suppose we want to calculate the sum of

func(x[i]) * func(y[j]) * func(z[k])

for all i, j, k, where func is some arbitrary function.

Obviously, the following code does the job

sum <- 0
for (i in 1:length(x)) {
    for (j in 1:length(y)) {
        for (k in 1:length(z)) {
            sum <- sum + func(x[i]) * func(y[j]) * func(z[k])
        }
    }
}

Also obviously, if you are used to the S way, the following code does the job too

sum <- 0
for (xi in x) {
    for (yj in y) {
        for (zk in z) {
            sum <- sum + func(xi) * func(yj) * func(zk)
        }
    }
}

But that wasn't the problem Dave and Glen wanted to solve. What they wanted was a general solution for any arbitrary (finite) bunch of vectors, not just for three. The only elegant solution is to use recursion.

My solution was the following (copied from the file fred.R)

fred <- function(w, ..., func = function(x) x) {
   if (identical(list(...), list())) return(sum(func(w)))
   sum <- 0
   for (ww in w) sum <- sum + func(ww) * fred(..., func = func)
   return(sum)
}

If you're not used to recursion, it's not obvious how this works. First it is clear that the sum can be written

∑_{i = 1}^length(x) f(x_i) × ∑_{j = 1}^length(y) f(y_j) × ∑_{k = 1}^length(z) f(z_k)

So it is clear the for loop in fred does the right thing assuming fred(..., func = func) does the right thing, which is to calculate however many sums remain, for example

∑_{j = 1}^length(y) f(y_j) × ∑_{k = 1}^length(z) f(z_k)

when the problem is given by the triple sum above and we are in the first call to fred. But the recursive call to fred does do the right thing, because that's the way recursive functions work!

The only remaining issue to discuss is the if test. We must have a test that stops the recursion. We don't want an infinite sequence of recursive calls, so we need a test to do the right thing without a recursive call at some point. Here the right place to stop the recursion is when there is no ... argument.

The file source does a few simple tests with results in the file source.Rout.