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.

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.