Prevent infinite recursion/stack overflow error in a recursive R function

Question

A simple recursive function is created as shown below.

power <- function(x, n) {
  if(n >= 1) x * power(x, n-1)
  else 1
}

When n is set to be 1e4, it shows an error of infinite recursion. As the error message suggests, I updated the option parameter and, in this case, stack overflow error is encountered.

## error to run power 10000 times with defalult option
options()$expressions
#[1] 5000

power(2, 1e3)
#[1] 1.071509e+301

power(2, 1e4)
#Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
#Error during wrapup: evaluation nested too deeply: infinite recursion / options(expressions=)?

## expressions parameter updated and results in stack overflow
options(expressions = 100000)
power(2, 1e4)
#Error: protect(): protection stack overflow

Scala supports tail recursion so that stack overflow error can be handled and I changed the function a bit as following.

## tail recursion supported in Scala
power.rec <- function(x, n, t = 1) {
  if(n < 1) t
  else power.rec(x, n-1, x*t)
}

It seems to get worse, however, as the updated function throws infinite recursion error when n is set to be 1e3. This is handled when the option parameter is increased but stack overflow error is encountered when n becomes 1e4.

# turn to default and even worse
options(expressions = 5000)
power.rec(2, 1e3)
#Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
#Error during wrapup: evaluation nested too deeply: infinite recursion / options(expressions=)?

# works in updated parameter
options(expressions = 100000)
power.rec(2, 1e3)
#[1] 1.071509e+301

# stack overflow error again
power.rec(2, 1e4)
#Error: protect(): protection stack overflow

Now my question is

How may it be possible to run this kind of functions without an error?

Thanks in advance.

Answer 1

Tail call optimization isn't implemented in R because R provides access to the full call stack. From Luke Tierney:

As to the question: 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.

The comment is somewhat old (2011) and I was hoping the compiler package would address this type of thing, but I could not get it to work. So you're left turning your function into a loop:

power.rec2 <- function(x, n, t = 1) {
  while(n > 0) {
    t <- x * t
    n <- n - 1
  }
  t
}
identical(power.rec(2, 10), power.rec2(2, 10))
# [1] TRUE
identical(power.rec(2, 1e2), power.rec2(2, 1e2))
# [1] TRUE
power.rec2(2, 1e3)
# [1] 1.071509e+301
power.rec2(2, 1e6)
# [1] Inf

Note tail recursion optimization does exactly this: turn a recursion into a loop. Unfortunately, you are left to do this manually.