Tail Recursion in R

Question

It seems I misunderstand tail recursion; according to https://stackoverflow.com/a/166268/312612/ does not support tail recursion. However, consider the following functions for calculating 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) } 

The "naive" recursive version:

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

And finally, I found that this should be a 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 look at the traces when calling these functions, this 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) response is displayed instantly and only one call is made. For FiboRecur(25) , thousands of calls are made, and they are launched within a few seconds before showing the result.

We can also see the runtime using the benchmark function from the rbenchmark package:

 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 happens in FiboRecurTail(25) , which makes it work as fast as the iterative version, and the “naive” recursive function works like molasses? Is it true that R supports tail recursion, but does not optimize the “naive” recursive version of a function that will be recursive, like other programming languages ​​(like Haskell)? Here is what I understand from this post on the R mailing list .

I would really appreciate it if someone missed the light in this. Thanks!

Answer 1

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

So you have many more function calls with the first. In the case of FiboRecurTail(25) you have a recursion depth of ~ 25 calls. FiboRecur(25) results in FiboRecur(25) function calls (including the first).

I did not run any of the routines, but note that you are showing 0.00 for both faster procedures. You should see some difference with a higher input value, but note that Fibo iterates exactly as much as FiboRecurTail recurses.

Answer 2

In the naive recursive approach, you recalculate many values. For example, when you compute FiboRecur(30) , you will compute FiboRecur(29) and FiboRecur(28) , and each of these two calls will be independent. And in FiboRecur(29) you again calculate FiboRecur(28) and FiboRecur(27) , although FiboRecur(28) already calculated elsewhere, as mentioned above. And this happens at every stage of the recursion. Or simply put, with each increase in n, the calculated force almost doubles, but, obviously, in fact it should be just as simple as combining the last two calculated numbers.

A short summary of FiboRecur(4) : FiboRecur(0) calculated twice, FiboRecur(1) calculated three times, FiboRecur(2) calculated twice, and FiboRecur(3) calculated once. The first three should really be calculated once and stored somewhere so that you can retrieve the values ​​whenever they are needed. And so you see so many function calls, even if it's not a big number.

However, in the recursive version of the tail, all previously calculated values ​​are passed to the next stage using the parameter a + b , which avoids countless repetitive calculations, as in the naive recursive version, and, therefore, is more efficient.