A few days ago I began learning Rust just for fun, and joined this forum to seek advice regarding books that might help. See Seeking Recommendations for an Introductory Book on Rust. After learning a little Rust from Chapter 2 of The Book and browsing through some code on various web sites, I decided to practice by writing a little program to work with the Golomb Sequence.
The On-Line Encyclopedia of Integer Sequences: A001462 describes the sequence succinctly as follows:
Golomb's sequence: a(n) is the number of times n occurs, starting with a(1) = 1.
This is the beginning of the sequence:
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, ...
Wikipedia provides some additional detail. See:
That Wikipedia article offers this recurrence relation:
a(1) = 1; a(n + 1) = 1 + a(n + 1 - a(a(n)))
Based on that relation, I have included a recursion in my program. The program prompts the user for a number, which we can call n, and computes and displays the value of the nth number in the sequence.
The recursive inner function employs a memoization, so that once each term in the sequence is computed, it can be saved for later lookup, which avoids having to compute the same terms repeatedly during the recursions.
I will probably add a loop later on that repeatedly prompts the user and displays results until the user enters an empty input.
Below is my code, so far, which does produce correct results. However, there is likely much additional room for improvement, so please offer any advice that might help this new learner become a better Rust programmer.
// Rust code to compute nth number in Golomb sequence
use std::io;
fn golomb(n: usize) -> usize { // work with unsigned integers
// wrapper function to contain recursive golomb_memoized function
fn golomb_memoized(n: usize, memo: &mut [Option<usize>]) -> usize {
// inner recursive function that maintains and uses memo
memo[n].unwrap_or_else(| | { // if there is an error, panic and stop program.
let res = {
if n > 1 { // recursive case
1 + golomb_memoized(n - golomb_memoized(golomb_memoized(n - 1, memo), memo), memo)
} else { // base case
1
}
};
memo[n] = Some(res); // error message said to wrap res in Some()
res
})
}
// return result of calling the inner golomb_memoized function
golomb_memoized(n, &mut vec![None; n + 1])
}
fn main() {
println!("Enter n (1 to 30000) to compute golomb(n):"); // avoid stack overflow
let mut inp = String::new();
io::stdin().read_line(&mut inp).expect("Could not read input");
// convert inp to an integer, store in n
let n: usize = inp.trim().parse().expect("Invalid input (needed an integer)");
let res = golomb(n);
println!("golomb({n}) is {res}.");
}