Does R support proper tail recursion and where can I find documentation about this?
Asked
Active
Viewed 2,063 times
3 Answers
19
It's quite easy to find out that R does not support tail recursion optimization:
f <- function(n) {
if (n != 0) f(n-1)
}
f(100000)
# Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
Had tail calls been optimized to jumps, then this function would have terminated without problems.
6
This reference, found easily with Google, suggests that R does not support tail recursion. Luke Tierney (R-core member and R internals expert) explains why:
tail call optimization cannot be applied in R, at least not in a simple way, because the semantics of R provide access to the call stack via the sys.xyz functions and parent.frame and such. It might be possible to make some semantic changes, such as only guaranteeing access to the immediate caller, but there isn't much point unless/until the performance of the function calling mechanism is improved.
Ben Bolker
- 211,554
- 25
- 370
- 453
duffymo
- 305,152
- 44
- 369
- 561
-
Just to be clear, that answer on R-devel was referring to tail call elimination. It did _not_ say recursion was impossible. – IRTFM Nov 03 '12 at 17:37
-
2"Proper" tail recursion I was referring to "tail call optimization/elimination". Considering R is a full statistical package, with real closures and some Object-Oriented features more aligned to functional programming (as "generic functions" and classes to this "generic functions") than to "traditional" imperative languages, it seemed strange, for me, it doesn't support tail call elimination. Anyway, I'll just avoid to use recursivity and I'll use loops. No problem, at all. – Paulo Silva Filho Nov 04 '12 at 23:13