是否可以在 Rust 中编译时计算递归函数?

Question

我想计算const的阶乘：

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

我认为在 Rust 1.18 中不起作用的解决方案是：

• const fn— 条件语句在const fn中是不允许的(或至少不是实现的)，所以这些都不会编译：

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

• 宏 ― 在所有宏扩展后执行表达式的计算。 这个宏永远不会达到基本情况，因为经过四次迭代后，参数是4-1-1-1-1的，它与0不匹配：

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

我还尝试了以下方法，如果*有短路评估，这将起作用，但原样具有无条件递归，这会产生堆栈溢出：

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

正如Matthieu M.指出的那样，我们可以通过使用factorial(n - ((n != 0) as usize))来避免整数下溢(但不能避免堆栈溢出)。

现在，我已经求助于手动计算阶乘。

Answer 1

自从您最初的问题以来，Rust 已经更新，现在支持const fn中的条件，因此前两个解决方案有效。请参阅 Rust 参考中的 Const 函数部分 这说明您可以在 const 函数中具有"对其他安全 const 函数的调用(无论是通过函数调用还是方法调用)"。

对于您的特定阶乘示例，您(至少)有几个选项。这是我成功编译的一个阶乘函数：

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

注意，n！其中 n> 20 将溢出一个u64，所以我决定在这种情况下返回 0。此外，由于usize可能是 32 位值，因此在这种情况下我显式使用 64 位u64。处理u64溢出情况还可以防止堆栈溢出。这可能会返回一个Option<u64>：

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

就我而言，返回Option<u64>限制了我使用该函数的方式，因此我发现仅返回一个带有 0 的u64作为None的类似物更有用。

Answer 2

> 这目前在特征const_fn下进行了探索，但现在你不能从另一个 const 函数调用一个函数，甚至是 const。

但是，您可以分解大枪：元编程(过程宏)以在编译时计算值。例如，我发现了这个板条箱(但没有测试它)。

这个关于编译时计算的 Rosetta Code 页面表明编译器可以进行一些编译时优化，但没有什么是可以保证的，这只是一种特殊情况。

Answer 3

[使用常量初始化进行编辑]

也可以使用 rust 类型系统来计算阶乘。Crate typenum 允许通过在类型系统的基础上重新编码二进制算术：

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

这导致：

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

阶乘类型 F0、F1、F2、F3 F4 F5、F20 当然是在编译时生成的。 然后使用与特征 Unsigned 关联的常量 USIZE 来初始化 usize 常量、FACT0、FACT1、...

好吧，这当然不是在编译时计算阶乘的最有效方法;const fn更好！然而，有趣的是，rust 类型系统足够强大，可以在编译时实现一些功能和递归计算！

这可能对其他任务有用。例如，当您必须处理一些算术时，它也是 const 泛型的一个有趣的替代方案(至少目前是这样)。通常，这种类型机制用于泛型数组或代数。