Tail recursion in R

Question

I seem to misunderstand tail recursion; according to this stackoverflow question R does not support tail recursion. However, let's consider the following functions to compute the nth fibonacci number:

Iterative version:

Fibo <- function(n){
    a <- 0
    b <- 1
    for (i in 1:n){
        temp <- b
        b <- a
        a <- a + temp
    }
    return(a)
}

"Naive" recursive version:

FiboRecur <- function(n){
    if (n == 0 || n == 1){
        return(n)
    } else {
        return(FiboRecur(n-1) + FiboRecur(n-2))
        }
}

And finally an example I found that should be tail call recursive:

FiboRecurTail <- function(n){
    fib_help <- function(a, b, n){
        if(n > 0){
            return(fib_help(b, a+b, n-1))
        } else {
            return(a)
        }
    }
    return(fib_help(0, 1, n))
}

Now if we take a look at the traces when these functions are called, here is what we get:

Fibo(25)
trace: Fibo(25)
[1] 75025


trace(FiboRecur)
FiboRecur(25)
Thousands of calls to FiboRecur and takes a lot of time to run

FiboRecurTail(25)
trace: FiboRecurTail(25)
[1] 75025

In the cases of Fibo(25) and FiboRecurTail(25), the answer is displayed instantaneously and only one call is made. For FiboRecur(25), thousands of calls are made and it runs for some seconds before showing the result.

We can also take a look at the run times using the benchmark function from the package rbenchmark:

benchmark(Fibo(30), FiboRecur(30), FiboRecurTail(30), replications = 5)
               test replications elapsed relative user.self sys.self user.child sys.child
1          Fibo(30)            5    0.00       NA     0.000        0          0         0
2     FiboRecur(30)            5   13.79       NA    13.792        0          0         0
3 FiboRecurTail(30)            5    0.00       NA     0.000        0          0         0

So if R does not support tail recursion, what is happening in FiboRecurTail(25) that makes it run as fast as the iterative version while the "naive" recursive function runs like molasses? Is it rather that R supports tail recursion, but does not optimize a "naive" recursive version of a function to be tail-call recursive like other programming languages (Haskell for instance) do? This is what I understand from this post in R's mailing list.

I would greatly appreciate if someone would shed some light into this. Thanks!

Answer 1

The difference is that for each recursion, FiboRecur calls itself twice. Within FiboRecurTail, fib_help calls itself only once.

Thus you have a whole lot more function calls with the former. In the case of FiboRecurTail(25) you have a recursion depth of ~25 calls. FiboRecur(25) results in 242,785 function calls (including the first).

I didn't time any of the routines, but note that you show 0.00 for both of the faster routines. You should see some difference with a higher input value, but note that Fibo iterates exactly as much as FiboRecurTail recurses.