recursion - 在 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 中的条件语句。 ，所以前两个解决方案有效。查看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 ，所以我决定在这种情况下返回 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>限制了我如何使用这个函数，所以我发现只返回一个 u64 更有用。用 0 模拟 None .