Хвостовая рекурсия по R Статистическая среда

Question

Поддерживает ли R правильную хвостовую рекурсию и где я могу найти документацию по этому поводу?

Answer 1

Довольно легко обнаружить, что R не поддерживает оптимизацию хвостовой рекурсии:

f <- function(n) {
if (n != 0) f(n-1)
}
f(100000)
# Error: evaluation nested too deeply: infinite recursion / options(expressions=)?

Если бы хвостовые вызовы были оптимизированы для переходов, то эта функция была бы завершена без проблем.

Answer 2

Нет, R не поддерживает хвостовую рекурсию.

Answer 3

Эта ссылка, которую легко найти в Google, предполагает, что R не поддерживает хвостовую рекурсию, и объясняет почему.

Answer 4

В разрабатываемой версии R (по состоянию на октябрь 2023 г.) появилась новая функциональность, которая позволяет R поддерживать исключение вызовов в хвостовой рекурсии с помощью методаTailcall()помощник:

Со страницы помощи :

С использованиемTailcallможно определить функции хвостовой рекурсии, которые не увеличивают стек вычислений... Преимущество этой оптимизации хвостовых вызовов заключается в том, что они не увеличивают стек вызовов и допускают произвольно глубокую хвостовую рекурсию.

Пример со страницы справки, вычисляющий log(10)-факториал:

      lfact <- function(n) {
    lfact_iter <- function(val, n) {
        if (n <= 0)
            val
        else {
            val <- val + log10(n) # forces val
            Tailcall(lfact_iter, val, n - 1)
        }
    }
    lfact_iter(0, n)
}
suppressWarnings(10 ^ lfact(3)) # first Tailcall in a session warns
lfact(100000)