当前位置：文江博客话题详情

在 Erlang 中使用大量尾递归会减慢速度吗？

发布于 2024-07-26 02:36:14 字数 124 浏览 7 评论 0原文

我最近一直在阅读有关 Erlang 的内容，以及由于使用迭代循环的困难而如何大量使用尾递归。

如此频繁地使用递归难道不会减慢它的速度吗？所有的函数调用及其对堆栈的影响是怎样的？或者尾递归是否否定了大部分内容？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

美人如玉 2024-08-02 02:36:14

重点是 Erlang 优化了尾部调用（不仅仅是递归）。优化尾部调用非常简单：如果返回值是通过调用另一个函数来计算的，那么这个另一个函数不仅放在调用函数顶部的函数调用堆栈上，而且还放在当前函数的堆栈帧上替换为被调用函数之一。这意味着尾部调用不会增加堆栈大小。

所以，不，使用尾递归不会减慢 Erlang 的速度，也不会带来堆栈溢出的风险。

通过尾调用优化，您不仅可以使用简单的尾递归，还可以使用多个函数的相互尾递归（a 尾调用 b，尾调用 c，尾调用 a ...）。有时这可能是一个很好的计算模型。

回复收藏 0 原文

蓝海似她心 2024-08-02 02:36:14

迭代尾递归通常使用尾调用来实现。
这基本上是递归调用到简单循环的转换。

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;
}

Iterative tail recursion is generally implemented using Tail calls.
This is basically a transformation of a recursive call to a simple loop.

C# example:

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);
};

or even better:

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

C# not real tail recursion, this is because the return value is modified, most compilers won't break this down into a loop:

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;
}

回复收藏 0 原文

活雷疯 2024-08-02 02:36:14

在大多数情况下，它不应该影响性能。您要寻找的不仅仅是尾部调用，而是尾部调用优化（或尾部调用消除）。尾调用优化是一种编译器或运行时技术，它确定对函数的调用何时相当于“弹出堆栈”以返回到正确的函数，而不仅仅是返回。一般来说，尾调用优化只能在递归调用是函数中的最后一个操作时才能进行，因此必须小心。

回复收藏 0 原文

橙味迷妹 2024-08-02 02:36:14

有一个与尾递归有关的问题，但它与性能无关 - Erlang 尾递归优化还涉及消除调试堆栈跟踪。

例如，请参阅 Erlang FAQ 的第 9.13 点：

为什么堆栈回溯没有显示此代码的正确函数：
-module(erl)。 
  -导出（[a/0]）。 

  a() ->;   b()。 
  b() ->;   C（）。 
  c() ->;   3 = 4. %% 会导致错误匹配 
  
堆栈回溯仅显示函数 c()，而不显示 a()、b() 和 c()。
这是因为最后调用优化；编译器知道它不需要
为 a() 或 b() 生成堆栈帧，因为它所做的最后一件事是调用另一个函数，因此堆栈帧不会出现在堆栈回溯中。

当你遇到崩溃时，这可能会有点痛苦（但这确实有点符合函数式编程的领域......）

There is a problem pertaining to tail-recursion but it is not related to performance - Erlang tail-recursion optimisation also involves elimination of the stack trace for debugging.

For instance see Point 9.13 of the 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.

This can be a bit of pain when you hit a crash (but it does kinda go with the territory of functional programming...)

回复收藏 0 原文