CODEWITHSUNDEEP
recursionrustflatten
stevensonmt
stevensonmt

Reputation: 732

Recursive function that returns a Vec

I continue to struggle with the concept of recursion. I have a function that takes a u64 and returns a Vec<u64> of factors of that integer. I would like to recursively call this function on each item in the Vec, returning a flattened Vec until the function returns Vec<self> for each item, i.e., each item is prime.

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

(The complete code)

This returns only the Vec of factors of the final iteration and also has no conditional that allows it to keep going until items are all prime.

The factoring_method is a congruence of squares that I'm pretty happy with. I'm certain there's lots of room for optimization, but I'm hoping to get a working version complete before refactoring. I think the recursion should in the congruence_of_squares — calling itself upon each member of the Vec it returns, but I'm not sure how to frame the conditional to keep it from doing so infinitely.

Upvotes: 1

Views: 916

Answers (1)

Shepmaster
Shepmaster

Reputation: 431809

Useful recursion requires two things:

  1. That a function call itself, either directly or indirectly.
  2. That there be some terminating case.

One definition of the prime factorization of a number is:

  • if the number is prime, that is the only prime factor
  • otherwise, combine the prime factors of a pair of factors of the number

From that, we can identify a termination condition ("if it's prime") and the recursive call ("prime factors of factors").

Note that we haven't written any code yet — everything to this point is conceptual.

We can then transcribe the idea to Rust:

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

Interesting pieces here:

  • We use into_iter to avoid the need to dereference the iterated value.
  • We can pass the function name directly as the closure because the types align.

Some (inefficient) helper functions round out the implementation:

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![],
    }
}

Upvotes: 2

Related Questions