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

Question

我想计算一个的阶乘const。我想结束这样的事情：

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

显而易见的解决方案（不起作用）是：

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

没有10！其中 n > 20 会溢出 a 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>有限的使用该函数的方式，所以我发现只返回 au64和 0 作为 的类似物更有用None。