递归函数计算因子导致堆栈溢出

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常见问题解答中阅读更多相关内容),但与此同时,您将不得不进行如此深入的渲染或使用循环.

Answer 2

为什么？

这是堆栈溢出,只要没有剩余堆栈内存就会发生.例如,堆栈内存使用

• 局部变量
• 函数参数
• 返回值

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

如何解决？

显而易见的解决方案是以非递归方式编写算法(当您想在生产中使用算法时,应该这样做!).但是你也可以增加堆栈大小.虽然无法修改主线程的堆栈大小,但您可以创建新线程并设置特定堆栈大小:

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():我num在每次factorial()调用时打印了函数参数的地址:

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

两个连续呼叫地址之间的差异是(或多或少)堆栈帧大小.在我的机器上,差异略小于0xFF(255),所以我只是用它作为大小.

如果你想知道为什么堆栈帧大小不小:Rust编译器并没有真正优化这个指标.通常它实际上并不重要,因此优化器倾向于牺牲这种内存需求以获得更好的执行速度.我看了一下装配,在这种情况下BigUint,内联了许多方法.这意味着其他函数的局部变量也在使用堆栈空间!

Answer 3

作为替代......(我不推荐)

Matts答案在某种程度上是正确的.有一个叫做stacker(这里)的箱子,可以人为地增加堆栈大小,以便在递归算法中使用.它通过分配一些堆内存溢出来实现这一点.

作为一个警告的话......这需要很长时间才能运行 ......但是,它会运行,并且不会使堆栈爆炸.使用优化进行编译会降低它,但它仍然很慢.正如马特建议的那样,你可能会从循环中获得更好的性能.无论如何,我以为我会把它扔出去.

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

我已经注释掉了调试println...如果你愿意,你可以取消注释它们.