Tail recursion on R Statistical Environment

Question

Does R support proper tail recursion and where can I find documentation about this?

score 18 · Accepted Answer · edited Aug 16 '16 at 16:25

18

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.

edited Aug 16 '16 at 16:25

Frank

answered Nov 03 '12 at 12:06

Fred Foo

score 6 · Answer 2 · answered Nov 03 '12 at 12:04

6

No, R does not support tail recursion.

answered Nov 03 '12 at 12:04

G. Grothendieck

score 6 · Answer 3 · answered Nov 03 '12 at 12:04

6

This reference, found easily with Google, suggests that R does not support tail recursion and explains why.

answered Nov 03 '12 at 12:04

duffymo

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

3 Answers3