返回Vec的递归函数

Question

我继续与递归的概念作斗争。我有一个函数，它接受一个u64，并返回该整数的因数的Vec<u64>。我想对Vec中的每一项递归调用此函数，返回一个展平的Vec，直到该函数为每一项返回Vec<self>，即每一项都是质数。

fn prime_factors(x: u64) -> Vec<u64> {
    let factors = factoring_method(x);
    factors.iter().flat_map(|&i| factoring_method(i)).collect()
}

(The complete code)

这只返回最终迭代的因子的Vec，并且也没有允许它继续运行的条件，直到所有项目都是质数。

factoring_method是一个我非常满意的方块的同余。我确信有很多优化的空间，但我希望在重构之前得到一个完整的工作版本。我认为递归应该在congruence_of_squares中调用它返回的Vec的每个成员，但是我不确定如何构造条件来防止它无限地这样做。

Answer 1

有用的递归需要两件事：

函数自身调用的一种方法，可以直接调用，也可以直接调用，也可以在某些情况下终止。

数的素因式分解的一个定义是：

如果数是素数，那就是唯一的素数因子组合成一对因子的素因数

由此，我们可以确定终止条件(“如果它是质数”)和递归调用(“因子的质数因子”)。

请注意，我们还没有编写任何代码，到目前为止，- everything只是概念性的。

然后我们可以将这个想法转录成Rust：

fn prime_factors(x: u64) -> Vec<u64> {
    if is_prime(x) {
        vec![x]
    } else {
        factors(x).into_iter().flat_map(prime_factors).collect()
    }
}

这里有一些有趣的东西：

• 我们使用into_iter来避免引用迭代值的需要。
• 我们可以将函数名作为闭包直接传递，因为类型是对齐的。

一些(低效)帮助器函数完善了实现：

fn is_prime(x: u64) -> bool {
    !(2..x).any(|i| x % i == 0)
}

fn factors(x: u64) -> Vec<u64> {
    match (2..x).filter(|i| x % i == 0).next() {
        Some(v) => vec![v, x / v],
        None => vec![],
    }
}