recursion - 返回 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

有用的递归需要两件事:

1. 函数直接或间接调用自身。
2. 存在一些终止情况。

素数分解的一个定义是:

• 如果数是素数，那是唯一的素数
• 否则，合并该数的一对因数的质因数

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

请注意，我们还没有编写任何代码——到目前为止，一切都是概念性的。

然后我们可以将这个想法转录成 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![],
    }
}