Is it possible to have a recursive function computed at compile-time in Rust?

Question

I want to compute the factorial of a const:

const N: usize = 4;
const N_PERMUTATIONS = factorial(N);

The solutions I've thought of that don't work in Rust 1.18 are:

• const fn — conditional statements are not allowed (or at least not implemented) in const fn, so neither of these will compile:

  const fn factorial(n: usize) -> usize {
      match n {
          0 => 1,
          _ => n * factorial(n-1)
      }
  }
  

  const fn factorial(n: usize) -> usize {
      if n == 0 {
          1
      } else {
          n * factorial(n-1)
      }
  }
  

• macros — evaluation of expressions is performed after all macro expansion. This macro will never reach the base case, since after four iterations the argument is 4-1-1-1-1, which is not matched by 0:

  macro_rules!factorial {
      (0) => (1);
      ($n:expr) => ($n * factorial($n-1));
  }
  

I also tried the following, which would work if * had short-circuit evaluation, but as-is has unconditional recursion which yields a stack overflow:

const fn factorial(n: usize) -> usize {
    ((n == 0) as usize) + ((n != 0) as usize) * n * factorial(n-1)
}

As Matthieu M. pointed out, we can avoid integer underflow (but not stack overflow) by using factorial(n - ((n != 0) as usize)).

For now I've resorted to manually computing the factorial.

Snuck

Is there anything preventing you from utilizing a build script? – Cassius

See also Is there a way to count with macros? – Cassius

You could perhaps manually compute it but write a test that asserts the dynamic computation? – Accomplished

The recursion here is unconditional, since you always call factorial. Multiplying n and 1 in factorial(n - 1) leads to a stackoverflow of the compiler => play.rust-lang.org/… – Anhedral

Possible duplicate of Is there a way to count with macros? – Snuck

Answer 1

Since your original question, Rust has been updated and now supports conditionals in const fn, so the first two solutions work. See the Const functions section in the Rust Reference which states that you can have "Calls to other safe const functions (whether by function call or method call)" in const functions.

For your particular factorial example, you have (at least) a couple options. Here is a factorial function that I have successfully compiled:

const fn factorial(n: u64) -> u64 {
    match n {
        0u64 | 1u64 => 1,
        2u64..=20u64 => factorial(n - 1u64) * n,
        _ => 0,
    }
}

Note, n! where n > 20 will overflow a u64, so I decided to return 0 in that case. Also, since usize could be a 32-bit value, I explicitly use the 64-bit u64 in this case. Handling the u64 overflow case also prevents the stack overflow. This could return an Option<u64> instead:

const fn factorial(n: u64) -> Option<u64> {
    match n {
        0u64 | 1u64 => Some(1),
        2u64..=20u64 => match factorial(n - 1u64) {
            Some(x) => Some(n * x),
            None => None,
        },
        _ => None,
    }
}

In my case, returning an Option<u64> limited how I could use the function, so I found it more useful to just return a u64 with 0 as the analogue to None.

Traject

Answer 2

This is currently explored under the feature const_fn, but for now you cannot call a function, even const, from another const function.

You can however break out the big guns: metaprogramming (procedural macro) to compute the value at compile-time. I found this crate for example (but did not test it, though).

This Rosetta Code page on compile time calculation shows that the compiler can do some compile-time optimization, but nothing is guaranteed, and this is only a particular case.

Reasonable

Answer 3

[EDIT with const initialization]

It is also possible to compute factorial by using rust type system. Crate typenum allows that by recoding binary arithmetic on the basis of the type system:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=d34eef48622363ca2096a246cd933554

use std::ops::{ Mul, Sub, };
use typenum::{
    B1, Sub1, Prod, U0, U1, U2, U3, U4, U5, U20, U24, Unsigned, Bit, UInt
};

trait Fact {
    type F: Unsigned;
}

impl Fact for U0 {
    type F = U1;
}

impl<U: Unsigned, B: Bit> Fact for UInt<U, B> where UInt<U, B>: Sub<B1>, 
        Sub1<UInt<U, B>>: Fact, UInt<U, B> : Mul<<Sub1<UInt<U, B>> as Fact>::F>,
        Prod<UInt<U, B>,<Sub1<UInt<U, B>> as Fact>::F>: Unsigned {
    type F = Prod<UInt<U, B>,<Sub1<UInt<U, B>> as Fact>::F>;
}

fn main() {
    type F0 = <U0 as Fact>::F;
    type F1 = <U1 as Fact>::F;
    type F2 = <U2 as Fact>::F;
    type F3 = <U3 as Fact>::F;
    type F4 = <U4 as Fact>::F;
    type F5 = <U5 as Fact>::F;
    type F20 = <U20 as Fact>::F;
    const FACT0: usize = F0::USIZE;
    const FACT1: usize = F1::USIZE;
    const FACT2: usize = F2::USIZE;
    const FACT3: usize = F3::USIZE;
    const FACT4: usize = F4::USIZE;
    const FACT5: usize = F5::USIZE;
    const FACT20: usize = F20::USIZE;
    println!("0! = {}", FACT0);
    println!("1! = {}", FACT1);
    println!("2! = {}", FACT2);
    println!("3! = {}", FACT3);
    println!("4! = {}", FACT4);
    println!("5! = {}", FACT5);
    println!("20! = {}\n", FACT20);
    println!("Binary structure:");
    println!("F4 = {:?}",F4::new());
    println!("U24 = {:?}\n",U24::new());

    fn print_u24(_: U24) {
        println!("type F4 is the same as type U24");
    }
    print_u24(F4::new());
}

which results in:

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
20! = 2432902008176640000

Binary structure:
F4 = UInt { msb: UInt { msb: UInt { msb: UInt { msb: UInt { msb: UTerm, lsb: B1 }, lsb: B1 }, lsb: B0 }, lsb: B0 }, lsb: B0 }
U24 = UInt { msb: UInt { msb: UInt { msb: UInt { msb: UInt { msb: UTerm, lsb: B1 }, lsb: B1 }, lsb: B0 }, lsb: B0 }, lsb: B0 }

type F4 is the same as type U24

The factorial types F0, F1, F2, F3 F4 F5, F20, are of course generated at compile time. Constant USIZE associated with trait Unsigned is then used to initialize usize constants, FACT0, FACT1, ...

Well, this is certainly not the most efficient way to compute a factorial at compilation time; const fn is better! However, it is interesting to see that rust typing system is sufficiently powerful to implement some functional and recursive computation at compile time!

This may be useful for other tasks. For example, it is also an interesting alternative to const generics when you have to deal with some arithmetic on it (at least for now). Typically, such typing mechanism are used in generic-array or in nalgebra.

Handwriting