Recursive function calculating factorials leads to

Question

I tried a recursive factorial algorithm in Rust. I use this version of the compiler:

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

Code:

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

I got this error:

$ cargo run

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

How to fix that? And why do I see this error when using Rust?

Answer 1

Rust doesn't have tail call elimination, so your recursion is limited by your stack size. It may be a feature for Rust in the future (you can read more about it at the Rust FAQ), but in the meantime you will have to either not recurse so deep or use loops.

Answer 2

Just as an alternative.. (I do not recommend)

Matts answer is true to an extent. There is a crate called stacker (here) that can artificially increase the stack size for usage in recursive algorithms. It does this by allocating some heap memory to overflow into.

As a word of warning... this takes a very long time to run ... but, it runs, and it doesn't blow the stack. Compiling with optimizations brings it down but its still pretty slow. You're likely to get better perf from a loop as Matt suggests. I thought I would throw this out there anyway.

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

I have commented out the debug printlns.. you can uncomment them if you like.

Answer 3

Why?

This is a stack overflow which occurs whenever there is no stack memory left. For example, stack memory is used by

• local variables
• function arguments
• return values

Recursion uses a lot of stack memory, because for every recursive call, the memory for all local variables, function arguments, ... has to be allocated on the stack.

---

How to fix that?

The obvious solution is to write your algorithm in a non-recursive manner (you should do this when you want to use the algorithm in production!). But you can also just increase the stack size. While the stack size of the main thread can't be modified, you can create a new thread and set a specific stack size:

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

This code works and, when executed via cargo run --release (with optimization!), outputs the solution after only a couple of seconds calculation.

---

Measuring stack frame size

In case you want to know how the stack frame size (memory requirement for one call) for factorial() was measured: I printed the address of the function argument num on each factorial() call:

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

The difference between two successive call's addresses is (more or less) the stack frame size. On my machine, the difference was slightly less than 0xFF (255), so I just used that as size.

In case you're wondering why the stack frame size isn't smaller: the Rust compiler doesn't really optimize for this metric. Usually it's really not important, so optimizers tend to sacrifice this memory requirement for better execution speed. I took a look at the assembly and in this case many BigUint methods were inlined. This means that the local variables of other functions are using stack space as well!