How to make this program not crash

help
1

There is a program, fn fib will cause stackoverflow in a thread, and it will cause the whole program crash.

How to make this program not crash, I want to capture the stack overflow error in fn main.

fn main() {
    let join_handle: std::thread::JoinHandle<()> = std::thread::spawn(|| {
        let result: u64 = fib(100000);
        println!("fib(100000) = {}", result);
    });
    let _ = join_handle.join();

    println!("main thread end")
}

fn fib(n: u64) -> u64 {
    match n {
        0 | 1 => n,
        _ => fib(n - 1) + fib(n - 2),
    }
}

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.03s
     Running `target/debug/rust-playground`

thread '<unknown>' has overflowed its stack
fatal runtime error: stack overflow
[1]    60542 IOT instruction (core dumped)  cargo run
2

You might find this thread interesting:

3

Don't use recursion.

Fundamentally, the problem is that with n = 100_000, you are going to blow through your stack pretty damn fast. I don't believe there's any cross-platform way to "catch" a stack overflow. You can apparently do it on Windows, but that requires you to be using C++ and MSVC. I couldn't find any way of doing it on *nix. Your only real option is to rewrite the code to not overflow the stack.

If you've never do so before, this would be an excellent opportunity to practice turning a recursive algorithm into an iterative one.

2 Likes
4

It's not feasible to (safely) catch stack overflows, but it is feasible to check before you recurse, so they don't happen.

1 Like
5

I agree. The best way to fix this is to rewrite it so as to not use recursion, such that it will not consume huge amounts of memory and not run terribly slowly. The common or garden high school math, iterative, algorithm is much better.

If you really want huge fibonacci numbers then use a far better algorithm for big numbers as described here: Fast Fibonacci algorithms, with an implementations in various languages here: GitHub - ZiCog/fibo_4784969: The million digit Fibonacci number challenge. Calculate fibo(4784969) in various languages.. C++, Javascript and Rust solutions by me.

These are recursive but recursion depth is orders of magnitude less.

1 Like
6

Rust solution by me :grinning:

1 Like
7

Sorry yes.

Now I remember: I had written, well almost written, a Rust solution myself but yours arrived first and was much better :slight_smile: So I threw mine away.

A big thanks for that. I should have noted contributors in the README.

Edit: I found my "discarded" Rust fibo(4784969) attempt. More truthful to say it was hardly started :frowning:

8

Fibonacci(100000) has 20899 decimal digits.

Fixing the stack overflow will only result in a integer overflow!

2 Likes
9

Thank you.