Предотвращение ошибки переполнения бесконечной рекурсии/стека в рекурсивной функции R

Question

Простая рекурсивная функция создается, как показано ниже.

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

При п устанавливается равным 1E4, он показывает ошибку infinite recursion. Как следует из сообщения об ошибке, я обновил параметр параметра, и в этом случае возникает ошибка stack overflow.

## 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 поддерживает хвостовую рекурсию, так что stack overflow ошибки может быть обработана и я изменил функцию немного следующим образом.

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

кажется, еще хуже, однако, как обновленная функция вызывает infinite recursion ошибку при п устанавливается равным 1e3. Это обрабатывается, когда параметр параметра увеличивается, но ошибка stack overflow возникает, когда n становится 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 

Теперь мой вопрос

Как это может быть возможным, чтобы запустить этот вид функций без ошибок?

Заранее спасибо.

Answer 1

Оптимизация звонков в R не реализована в R, так как R обеспечивает доступ к полному стеку вызовов. От Luke Tierney:

Что касается вопроса: оптимизация хвоста вызова не может быть применена в R, по крайней мере, не простой способом, так как семантика R обеспечивает доступ к стеке вызовов с помощью функций sys.xyz и parent.frame и т. д. Возможно, возможно внести некоторые семантические изменения, например, только гарантировать доступ к непосредственному вызывающему абоненту, но не так много, если/до тех пор, пока не улучшится производительность механизма вызова функции.

Комментарий несколько старых (2011), и я надеялся, что compiler пакет будет рассматривать этот тип вещи, но я не мог заставить его работать. Таким образом, вы остаетесь поворачивая функцию в петлю:

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 

Примечание оптимизации хвостовой рекурсии делает именно это: превратить рекурсии в петлю. К сожалению, вам нужно сделать это вручную.