Rust 何时保证尾递归？
When is tail recursion guaranteed in Rust?
C语言
在C语言中，很容易有尾递归:
int foo(...) {
return foo(...);
}
只是 return 作为递归调用的 return 值。当这种递归可能重复一千次甚至一百万次时，这一点尤为重要。它会在堆栈上使用大量 内存 。
生锈
现在，我有一个可以递归调用自身一百万次的 Rust 函数：
fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
match input.read(&mut [0u8]) {
Ok ( 0) => Ok(()),
Ok ( _) => read_all(input),
Err(err) => Err(err),
}
}
（这是一个最小的例子，真实的例子更复杂，但抓住了主要思想）
这里，递归调用的return值按原样return编辑，但是：
是否保证 Rust 编译器将应用尾递归？
例如，如果我们声明一些需要销毁的变量，如std::Vec，它是在递归调用之前销毁（允许尾递归）还是在递归调用之后销毁returns（禁止尾递归）？
tail recursion (reusing a stack frame for a tail call to the same function) nor tail call optimization（重用堆栈帧用于对 any 函数的尾调用）都不是 Rust 保证的，尽管优化器 可能 选择执行它们。
if we declare some variable that needs to be destroyed
据我了解，这是症结之一，因为更改已销毁堆栈变量的位置会引起争议。
另请参阅：
解释说，在 Rust 中，尾调用消除只是一种优化，而不是保证。但“永远不会保证”并不意味着“永远不会发生”。让我们看看编译器对一些真实代码做了什么。
是否发生在这个函数中？
截至目前，Compiler Explorer 上可用的最新 Rust 版本是 1.39，它不会 消除 read_all 中的尾调用。
example::read_all:
push r15
push r14
push rbx
sub rsp, 32
mov r14, rdx
mov r15, rsi
mov rbx, rdi
mov byte ptr [rsp + 7], 0
lea rdi, [rsp + 8]
lea rdx, [rsp + 7]
mov ecx, 1
call qword ptr [r14 + 24]
cmp qword ptr [rsp + 8], 1
jne .LBB3_1
movups xmm0, xmmword ptr [rsp + 16]
movups xmmword ptr [rbx], xmm0
jmp .LBB3_3
.LBB3_1:
cmp qword ptr [rsp + 16], 0
je .LBB3_2
mov rdi, rbx
mov rsi, r15
mov rdx, r14
call qword ptr [rip + example::read_all@GOTPCREL]
jmp .LBB3_3
.LBB3_2:
mov byte ptr [rbx], 3
.LBB3_3:
mov rax, rbx
add rsp, 32
pop rbx
pop r14
pop r15
ret
mov rbx, rax
lea rdi, [rsp + 8]
call core::ptr::real_drop_in_place
mov rdi, rbx
call _Unwind_Resume@PLT
ud2
注意这一行：call qword ptr [rip + example::read_all@GOTPCREL]。那就是（尾部）递归调用。从它的存在可以看出，它并没有被淘汰。
Compare this to an equivalent function with an explicit loop:
pub fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
loop {
match input.read(&mut [0u8]) {
Ok ( 0) => return Ok(()),
Ok ( _) => continue,
Err(err) => return Err(err),
}
}
}
没有要消除的尾调用，因此编译为一个函数，其中只有一个 call（到 input.read 的计算地址）。
哦，好吧。也许 Rust 不如 C。或者是吗？
它发生在 C 中吗？
这是一个 C 语言的尾递归函数，它执行非常相似的任务：
int read_all(FILE *input) {
char buf[] = {0, 0};
if (!fgets(buf, sizeof buf, input))
return feof(input);
return read_all(input);
}
这对于编译器来说应该非常容易消除。递归调用就在函数的底部，C 不必担心 运行 析构函数。但尽管如此，there's that recursive tail call，恼人的是没有被淘汰：
call read_all
事实证明，在 C 中也不能保证尾调用优化。我在不同的优化级别下尝试了 Clang 和 gcc，但我没有尝试将这个相当简单的递归函数变成循环。
曾经发生过吗？
好的，所以不能保证。编译器完全可以做到吗？是的！这是一个通过尾递归内部函数计算斐波那契数的函数：
pub fn fibonacci(n: u64) -> u64 {
fn fibonacci_lr(n: u64, a: u64, b: u64) -> u64 {
match n {
0 => a,
_ => fibonacci_lr(n - 1, a + b, a),
}
}
fibonacci_lr(n, 1, 0)
}
不仅消除了尾部调用，而且整个 fibonacci_lr 函数内联到 fibonacci 中，仅产生 12 条指令（看不到 call）：
example::fibonacci:
push 1
pop rdx
xor ecx, ecx
.LBB0_1:
mov rax, rdx
test rdi, rdi
je .LBB0_3
dec rdi
add rcx, rax
mov rdx, rcx
mov rcx, rax
jmp .LBB0_1
.LBB0_3:
ret
如果你compare this to an equivalent while loop，编译器生成几乎相同的程序集。
有什么意义？
你可能不应该依赖优化来消除尾调用，无论是在 Rust 还是在 C 中。它发生时很好，但如果你需要确保一个函数编译成一个紧密的循环，最可靠的至少现在，方法是使用循环。
C语言
在C语言中，很容易有尾递归:
int foo(...) {
return foo(...);
}
只是 return 作为递归调用的 return 值。当这种递归可能重复一千次甚至一百万次时，这一点尤为重要。它会在堆栈上使用大量 内存 。
生锈
现在，我有一个可以递归调用自身一百万次的 Rust 函数：
fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
match input.read(&mut [0u8]) {
Ok ( 0) => Ok(()),
Ok ( _) => read_all(input),
Err(err) => Err(err),
}
}
（这是一个最小的例子，真实的例子更复杂，但抓住了主要思想）
这里，递归调用的return值按原样return编辑，但是：
是否保证 Rust 编译器将应用尾递归？
例如，如果我们声明一些需要销毁的变量，如std::Vec，它是在递归调用之前销毁（允许尾递归）还是在递归调用之后销毁returns（禁止尾递归）？
tail recursion (reusing a stack frame for a tail call to the same function) nor tail call optimization（重用堆栈帧用于对 any 函数的尾调用）都不是 Rust 保证的，尽管优化器 可能 选择执行它们。
if we declare some variable that needs to be destroyed
据我了解，这是症结之一，因为更改已销毁堆栈变量的位置会引起争议。
另请参阅：
是否发生在这个函数中？
截至目前，Compiler Explorer 上可用的最新 Rust 版本是 1.39，它不会 消除 read_all 中的尾调用。
example::read_all:
push r15
push r14
push rbx
sub rsp, 32
mov r14, rdx
mov r15, rsi
mov rbx, rdi
mov byte ptr [rsp + 7], 0
lea rdi, [rsp + 8]
lea rdx, [rsp + 7]
mov ecx, 1
call qword ptr [r14 + 24]
cmp qword ptr [rsp + 8], 1
jne .LBB3_1
movups xmm0, xmmword ptr [rsp + 16]
movups xmmword ptr [rbx], xmm0
jmp .LBB3_3
.LBB3_1:
cmp qword ptr [rsp + 16], 0
je .LBB3_2
mov rdi, rbx
mov rsi, r15
mov rdx, r14
call qword ptr [rip + example::read_all@GOTPCREL]
jmp .LBB3_3
.LBB3_2:
mov byte ptr [rbx], 3
.LBB3_3:
mov rax, rbx
add rsp, 32
pop rbx
pop r14
pop r15
ret
mov rbx, rax
lea rdi, [rsp + 8]
call core::ptr::real_drop_in_place
mov rdi, rbx
call _Unwind_Resume@PLT
ud2
注意这一行：call qword ptr [rip + example::read_all@GOTPCREL]。那就是（尾部）递归调用。从它的存在可以看出，它并没有被淘汰。
Compare this to an equivalent function with an explicit loop:
pub fn read_all(input: &mut dyn std::io::Read) -> std::io::Result<()> {
loop {
match input.read(&mut [0u8]) {
Ok ( 0) => return Ok(()),
Ok ( _) => continue,
Err(err) => return Err(err),
}
}
}
没有要消除的尾调用，因此编译为一个函数，其中只有一个 call（到 input.read 的计算地址）。
哦，好吧。也许 Rust 不如 C。或者是吗？
它发生在 C 中吗？
这是一个 C 语言的尾递归函数，它执行非常相似的任务：
int read_all(FILE *input) {
char buf[] = {0, 0};
if (!fgets(buf, sizeof buf, input))
return feof(input);
return read_all(input);
}
这对于编译器来说应该非常容易消除。递归调用就在函数的底部，C 不必担心 运行 析构函数。但尽管如此，there's that recursive tail call，恼人的是没有被淘汰：
call read_all
事实证明，在 C 中也不能保证尾调用优化。我在不同的优化级别下尝试了 Clang 和 gcc，但我没有尝试将这个相当简单的递归函数变成循环。
曾经发生过吗？
好的，所以不能保证。编译器完全可以做到吗？是的！这是一个通过尾递归内部函数计算斐波那契数的函数：
pub fn fibonacci(n: u64) -> u64 {
fn fibonacci_lr(n: u64, a: u64, b: u64) -> u64 {
match n {
0 => a,
_ => fibonacci_lr(n - 1, a + b, a),
}
}
fibonacci_lr(n, 1, 0)
}
不仅消除了尾部调用，而且整个 fibonacci_lr 函数内联到 fibonacci 中，仅产生 12 条指令（看不到 call）：
example::fibonacci:
push 1
pop rdx
xor ecx, ecx
.LBB0_1:
mov rax, rdx
test rdi, rdi
je .LBB0_3
dec rdi
add rcx, rax
mov rdx, rcx
mov rcx, rax
jmp .LBB0_1
.LBB0_3:
ret
如果你compare this to an equivalent while loop，编译器生成几乎相同的程序集。
有什么意义？
你可能不应该依赖优化来消除尾调用，无论是在 Rust 还是在 C 中。它发生时很好，但如果你需要确保一个函数编译成一个紧密的循环，最可靠的至少现在，方法是使用循环。