递归函数计算阶乘导致栈溢出

Question

我在 Rust 中尝试了递归阶乘算法。我用的是这个版本的编译器：

rustc 1.12.0 (3191fbae9 2016-09-23)
cargo 0.13.0-nightly (109cb7c 2016-08-19)

代码：

extern crate num_bigint;
extern crate num_traits;

use num_bigint::{BigUint, ToBigUint};
use num_traits::One;

fn factorial(num: u64) -> BigUint {
    let current: BigUint = num.to_biguint().unwrap();
    if num <= 1 {
        return One::one();
    }
    return current * factorial(num - 1);
}

fn main() {
    let num: u64 = 100000;
    println!("Factorial {}! = {}", num, factorial(num))
}

我收到这个错误：

$ cargo run

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
error: Process didn't exit successfully

如何解决？为什么我在使用 Rust 时会看到此错误？

Answer 1

Rust 没有尾调用消除，因此您的递归受堆栈大小的限制。它可能是 Rust 将来的一个特性（你可以在 Rust FAQ 阅读更多关于它的信息），但与此同时你将不得不要么不那么深入地递归，要么使用循环。

Answer 2

为什么？

这是堆栈溢出，只要没有剩余的堆栈内存就会发生。例如，堆栈内存被

使用

局部变量
函数参数
return 值

递归使用大量堆栈内存，因为对于每个递归调用，所有局部变量、函数参数...的内存都必须在堆栈上分配。

How to fix that?

显而易见的解决方案是以非递归方式编写您的算法（当您想在生产中使用该算法时，您应该这样做！）。但您也可以 增加筹码量 。虽然主线程的堆栈大小无法修改，但您可以创建一个新线程并设置特定的堆栈大小：

fn main() {
    let num: u64 = 100_000;
    // Size of one stack frame for `factorial()` was measured experimentally
    thread::Builder::new().stack_size(num as usize * 0xFF).spawn(move || {
        println!("Factorial {}! = {}", num, factorial(num));
    }).unwrap().join();
}

此代码有效并且，当通过 cargo run --release 执行时（经过优化！），只需几秒钟的计算即可输出解决方案。

正在测量堆栈帧大小

如果您想知道如何测量 factorial() 的堆栈帧大小（one 调用的内存要求）：我打印了函数参数的地址num 每次 factorial() 调用：

fn factorial(num: u64) -> BigUint {
    println!("{:p}", &num);
    // ...
}

两个连续调用地址之间的差异（或多或少）是堆栈帧的大小。在我的机器上，差异略小于 0xFF (255)，所以我只是将其用作大小。

如果你想知道为什么堆栈帧大小没有变小：Rust 编译器并没有真正针对这个指标进行优化。通常它真的不重要，所以优化器倾向于牺牲这个内存需求以获得更好的执行速度。我查看了程序集，在本例中内联了许多 BigUint 方法。这意味着其他函数的局部变量也在使用堆栈space！

Answer 3

作为替代..（我不推荐）

马茨的回答在一定程度上是正确的。有一个名为 stacker (here) 的箱子可以人为地增加堆栈大小以用于递归算法。它通过分配一些堆内存溢出来做到这一点。

作为一个警告...这需要 很长时间才能运行...但是，它运行s，它不会炸毁堆栈。通过优化进行编译会降低它的性能，但它仍然很慢。正如马特建议的那样，您可能会从循环中获得更好的性能。我想无论如何我都会把它扔出去。

extern crate num_bigint;
extern crate num_traits;
extern crate stacker;

use num_bigint::{BigUint, ToBigUint};
use num_traits::One;

fn factorial(num: u64) -> BigUint {
    // println!("Called with: {}", num);
    let current: BigUint = num.to_biguint().unwrap();
    if num <= 1 {
        // println!("Returning...");
        return One::one();
    }

    stacker::maybe_grow(1024 * 1024, 1024 * 1024, || {
        current * factorial(num - 1)
    })
}

fn main() {
    let num: u64 = 100000;
    println!("Factorial {}! = {}", num, factorial(num));
}

我已经注释掉了调试 printlns.. 如果您愿意，可以取消注释。

递归函数计算阶乘导致栈溢出

Recursive function calculating factorials leads to stack overflow

biginteger

bignum

factorial

rust

为什么？

How to fix that?

正在测量堆栈帧大小