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

macros — 表达式的计算在所有宏扩展之后执行。这个宏永远不会达到基本情况，因为在四次迭代之后参数是 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

目前在功能 const_fn 下对此进行了探索，但目前您不能从另一个 const 函数调用一个函数，甚至是 const。

然而，您可以使用大炮：元编程（过程宏）在编译时计算值。例如，我找到了 this crate（但没有测试）。

This Rosetta Code page on compile time calculation表明编译器可以一些编译时优化，但不能保证，这只是一个特例。

Answer 2

由于您最初的问题，Rust 已经更新并且现在支持 const fn 中的条件，因此前两个解决方案有效。查看 Const functions section in the Rust Reference 其中指出您可以在 const 函数中“调用其他安全的 const 函数（无论是通过函数调用还是方法调用）”。

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

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

注意，n！其中 n > 20 将溢出 u64，所以在这种情况下我决定 return 0。此外，由于 usize 可能是 32 位值，因此在本例中我明确使用 64 位 u64。处理 u64 溢出情况也可以防止堆栈溢出。这可以 return 和 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,
    }
}

在我的例子中，returning 一个 Option<u64> 限制了我如何使用这个函数，所以我发现只 return 一个 u64 和 0 更有用类似于 None.

Answer 3

[使用 const 初始化进行编辑]

也可以使用 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 当然是在编译时生成的。然后使用与 trait Unsigned 关联的常量 USIZE 来初始化 usize 常量，FACT0，FACT1，...

好吧，这肯定不是在编译时计算阶乘的最有效方法； const fn 更好！然而，有趣的是，Rust 类型系统足够强大，可以在编译时实现一些函数式和递归计算！

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

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

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

macros

recursion

constants

compile-time-constant

rust