These two sequences of positive integers are defined as:

 







R
(
1
)



=
1
 
;
 
S
(
1
)
=
2




R
(
n
)



=
R
(
n
−
1
)
+
S
(
n
−
1
)
,

n
>
1.






{\displaystyle {\begin{aligned}R(1)&=1\ ;\ S(1)=2\\R(n)&=R(n-1)+S(n-1),\quad n>1.\end{aligned}}}




The sequence 



S
(
n
)


{\displaystyle S(n)}

 is further defined as the sequence of positive integers not present in 



R
(
n
)


{\displaystyle R(n)}

.

Sequence 



R


{\displaystyle R}

 starts:

   1, 3, 7, 12, 18, ...

Sequence 



S


{\displaystyle S}

 starts:

   2, 4, 5, 6, 8, ...



Task

 Create two functions named ffr and ffs that when given n return R(n) or S(n) respectively.
(Note that R(1) = 1 and S(1) = 2 to avoid off-by-one errors).
 No maximum value for n should be assumed.
 Calculate and show that the first ten values of R are:
 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69
 Calculate and show that the first 40 values of ffr plus the first 960 values of ffs include all the integers from 1 to 1000 exactly once.


References

 Sloane's A005228 and A030124.
 Wolfram MathWorld
 Wikipedia: Hofstadter Figure-Figure sequences.


 
use std::collections::HashMap;
 
struct Hffs {
    sequence_r: HashMap<usize, usize>,
    sequence_s: HashMap<usize, usize>,
}
 
impl Hffs {
    fn new() -> Hffs {
        Hffs {
            sequence_r: HashMap::new(),
            sequence_s: HashMap::new(),
        }
    }
    fn ffr(&mut self, n: usize) -> usize {
        // first try the cache
        let new_r = if let Some(result) = self.sequence_r.get(&n) {
            *result
        } else if n == 0 {
            1
        } else {
            // call recursively
            self.ffr(n - 1) + self.ffs(n - 1)
        };
 
        // insert into the cache and return value
        *self.sequence_r.entry(n).or_insert(new_r)
    }
 
    fn ffs(&mut self, n: usize) -> usize {
        // first try the cache
        let new_s = if let Some(result) = self.sequence_s.get(&n) {
            *result
        } else if n == 0 {
            2
        } else {
            let lower = self.ffs(n - 1) + 1_usize;
            let upper = self.ffr(n) + 1_usize;
            let mut min_s: usize = 0;
            // find next available S
            for i in lower..=upper {
                if !self.sequence_r.values().any(|&val| val == i) {
                    min_s = i;
                    break;
                }
            }
            min_s
        };
 
        // insert into the cache and return value
        *self.sequence_s.entry(n).or_insert(new_s)
    }
}
 
impl Default for Hffs {
    fn default() -> Self {
        Self::new()
    }
}
fn main() {
    let mut hof = Hffs::new();
 
    for i in 0..10 {
        println!("H:{} -> R: {}, S: {}", i, hof.ffr(i), hof.ffs(i));
    }
 
    let r40 = (0..40).map(|i| hof.ffr(i)).collect::<Vec<_>>();
    let mut s960 = (0..960).map(|i| hof.ffs(i)).collect::<Vec<_>>();
 
    s960.extend(&r40);
    s960.sort_unstable();
    let f1000 = (1_usize..=1000).collect::<Vec<_>>();
 
    assert_eq!(f1000, s960, "Does NOT match");
}
 