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?

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.