Rust Recursion Practice

Rust

While working on a different project, I came across this puzzle.

Given a set of values, compute its full set of combinations.

Note that a “Combination” is a group of values where order of the values does not matter. Ex: ‘123’
We are NOT computing a set of “Permutations”. Ex: ‘123’ and ‘213’ and ‘321’ etc.

So, for example, we want to compute the set of combinations for the values 1,2,3 we can easily list them out by hand.
1, 12, 13, 14, 123, 124, 134, 1234, 2, 23, 24, 234, 3, 34, 4

There are 2^(n)-1 or 15 total combinations. Easy enough right?
What about values 1 to 5? That’s 31 combinations.
what about values 1 to 999? I’d spend the rest of my lifetime writing out that list.

How do we write a program to do this for us?

We know we need a loop for the most significant digit… and going deeper, we assume we need another loop for the second most significant digit… deeper still means more loops… MOOAARR LOOPS.

Writing 999 loops is definitely easier than writing out each combination by hand, but I still don’t want to write out 999 loops.

If we were only computing a single value result, we might think about solving this problem mathematically and avoid loops altogether. But instead, we need to record a combination at each step of the process.

The technique for solving these types of “loops on loops on loops” problems is called “Recursion”.

What recursion in programming looks like is a function, that during its execution, calls itself.

1
2
3
fn recursive_function() {
  recursive_function();
}

We can use a recursive function to perform our loops within loops within loops and record a combination at each step.

Solving the problem.

Let’s start our program by defining our start and end values from the first example above.

We’ll also create a Vec that will hold our result.

1
2
3
let start = 1;
let end = 4;
let mut collection: Vec<Vec<usize>> = Vec::new();

For the meat and potatoes of our program, we need a loop that serves the purpose of “given a number, calculate all combinations of values >= this number”. Ex: Given 1, calculate 1, 12, 123, 1234, 13, etc.

1
2
3
4
5
// end+1 because Rust for-loop endings are non-inclusive
for i in start..end+1
{
  // Something here will perform the computations.
}

Inside of the loop, we’ll put our recursive function… the recursive function… the recursive…

What kind of recursive function will solve this problem?

Since each call to the recursive function needs to know the part of the problem it’s supposed to work on, we need to give it the current position of the overall problem. We’ll call it pos for position. Ex. pos of ‘2’ will work on 2,23,234,24

We also need to keep track of the history of numbers that came before our recursive function call. We’ll call that history prefix. If pos is ‘3’, then prefix could be ‘1’ or ‘12’ or ‘2’.

We need to know how many times we need to repeat the inner loops ( current position to the end), so we’ll keep passing the end variable we created earlier.

Finally, we need a place to record our results from each step. We’ll pass a reference to our mutable collections vector along as well.

The code for the recursive function ends up looking like this:

1
2
3
4
5
6
7
8
9
10
11
12
13
fn recurse( pos: usize, end: usize, mut prefix: Vec<usize>, mut collection: &mut Vec<Vec<usize>>) {
  // push the current pos onto the prefix
  prefix.push(pos);
  // repeat the recursion for all values from pos to end
  for i in pos+1..end+1 {
    // we need a copy of the prefix to pass into the next recursion
    let newprefix = prefix.clone();
    // recurse the same function and blow our minds with convenience
    recurse( i, end, newprefix, collection);
  }
  // for each step of recursion, push the prefix (now a combination) into the collection.
  collection.push(prefix);
}

Putting it all together into a working program…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
fn main() {
  let start = 1;
  let end = 4;
  let mut collection: Vec<Vec<usize>> = Vec::new();
  for i in start..end+1
  {
      let prefix: Vec<usize> = Vec::new();
      recurse( i, end, prefix, &mut collection );
  }
  println!("{:?}",collection);
}
fn recurse( pos: usize, end: usize, mut prefix: Vec<usize>, mut collection: &mut Vec<Vec<usize>>) {
    prefix.push(pos);
    for i in pos+1..end+1 {
        let newprefix = prefix.clone();
        recurse( i, end, newprefix, collection);
    }
    collection.push(prefix);
}

The result comes out just as we wanted. By printing the Collection we see it contains all combinations for the values 1 to 4.

1
[[1, 2, 3, 4], [1, 2, 3], [1, 2, 4], [1, 2], [1, 3, 4], [1, 3], [1, 4], [1], [2, 3, 4], [2, 3], [2, 4], [2], [3, 4], [3], [4]]

Recursive functions are great for solving these types of problems.

Warning

Because we retain and build data at each step of the recursion, we quickly consume a large amount of memory as the value of end increases.

Share Comments