Замедляет ли использование большого количества хвостовой рекурсии в Erlang?

Question

Я недавно читал об Эрланге и о том, как хвостовая рекурсия так интенсивно используется из-за сложности использования итерационных циклов.

Не замедляет ли это активное использование рекурсии, что со всеми вызовами функций и их эффектом в стеке? Или рекурсия хвоста сводит на нет большую часть этого?

Answer 1

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

Таким образом, нет, использование хвостовой рекурсии не замедляет Эрланга и не создает риск переполнения стека.

При наличии оптимизации хвостового вызова вы можете не только использовать простую хвостовую рекурсию, но и взаимную хвостовую рекурсию нескольких функций (хвостовые вызовы b, которые хвостовые вызовы c, которые хвостовые вызовы a ...). Иногда это может быть хорошей моделью вычислений.

Answer 2

Итеративная хвостовая рекурсия обычно реализуется с использованием Хвостовых вызовов . По сути, это преобразование рекурсивного вызова в простой цикл.

C # пример:

uint FactorialAccum(uint n, uint accum) {
    if(n < 2) return accum;
    return FactorialAccum(n - 1, n * accum);
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

до

uint FactorialAccum(uint n, uint accum) {
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};
uint Factorial(uint n) {
    return FactorialAccum(n, 1);
};

или даже лучше:

uint Factorial(uint n) {
    uint accum = 1;
start:
    if(n < 2) return accum;
    accum *= n;
    n -= 1;
goto start;
};

---

C # не реальная хвостовая рекурсия, это потому, что возвращаемое значение модифицируется, большинство компиляторов не разбивают это на цикл:

int Power(int number, uint power) {
    if(power == 0) return 1;
    if(power == 1) return number;
    return number * Power(number, --power);
}

до

int Power(int number, uint power) {
    int result = number;
start:
    if(power == 0) return 1;
    if(power == 1) return number;
    result *= number;
    power--;
goto start;
}

Answer 3

Это не должно влиять на производительность в большинстве случаев. То, что вы ищете, это не просто хвостовые вызовы, а оптимизация хвостовых вызовов (или устранение хвостовых вызовов). Оптимизация вызова хвоста - это метод компиляции или времени выполнения, который выясняет, когда вызов функции является эквивалентом «извлечения стека» для возврата к нужной функции вместо простого возврата. Как правило, оптимизацию хвостового вызова можно выполнить только тогда, когда рекурсивный вызов является последней операцией в функции, поэтому вам следует быть осторожным.

Answer 4

Существует проблема, связанная с хвостовой рекурсией, но она не связана с производительностью. Оптимизация хвостовой рекурсии Erlang также включает устранение трассировки стека для отладки.

Например, см. Пункт 9.13 Erlang FAQ :

Why doesn't the stack backtrace show the right functions for this code:

        -module(erl).
        -export([a/0]).

        a() -> b().
        b() -> c().
        c() -> 3 = 4.           %% will cause badmatch

The stack backtrace only shows function c(), rather than a(), b() and c().
This is because of last-call-optimisation; the compiler knows it does not need
to generate a stack frame for a() or b() because the last thing it did was
call another function, hence the stack frame does not appear in the stack
backtrace.

Это может быть немного больно, когда вы попадаете в аварию (но это действительно похоже на территорию функционального программирования ...)

Answer 5

Аналогичная оптимизация, которая отделяет вызовы текстовых функций программы от вызовов функций реализации, - это «встраивание». В современных / продуманных языках вызовы функций мало связаны с вызовами функций машинного уровня.