Recursive function calculating factorials leads to stack overflow

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?

Eosin

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.

Durwyn

Great answer! But there are another problem with loop for factorial bigint - extremly slow. – Eosin

@Eosin I don't doubt it! But recursion, at least in Rust, doesn't really offer any speed improvements over loops. At least I haven't heard of that. – Durwyn

@Eosin Although LLVM can optimize certain tail calls, the function in the question does not have a tail call and would not be optimized anyway, even in a language that guaranteed TCO – Hoodwink

Answer 2

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!

Spiracle

Note: much like that famous cat, measuring stack frame size may increase it (before the address of num was taken, it could leave in a register, and println! requires some stack space too). – Oblation

Answer 3

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.

Selfexamination

maybe_grow(1024 * 1024, 1024 * 1024 will allocate a new stack frame every call. I measure 1GB memory usage. If I change it into maybe_grow(32 * 1024, 1024 * 1024, it will not allocate a new stack until 32K is left. Now it uses just 20MB memory. That change does not really change the speed though. – Depolarize

Ah yes sorry - I did originally have it at a 64k boundary but bumped it up on my final test. – Selfexamination

You say I do not recommend, but I think this is really a good option if you can't rewrite a recursive algorithm into an iterative algorithm. A runtime stack overflow is really bad. Of course the algorithm in this question is easy to write iterative. – Depolarize