# How to make integer array by a recurrence relation

How to generate Vec<u32> with a recurrence relation like a[n]=3a[n-1]+1, a[0] = 1 bounded by 1000?
Following code does but is there any better way? (does it use fold or something?)

let mut v = vec![];
let mut next = 1;
let f = |x: u32| x * 3 + 1;
loop {
if next > 1000 {
break;
}
v.push(next);
next = f(next);
}
// v = [1, 4, 13, 40, 121, 364]

cf. Haskell:

takeWhile (<= 1000) \$ iterate (\x -> x*3 + 1) 1

Thanks.

There are a couple ways. You can use a normal for loop similar to what youâ€™ve already done. Otherwise you can even create your own iterator and build on top of all the really powerful iterator combinators.

Iâ€™m on my phone at the moment, but the most idiomatic solution would look somewhat like this.

Here is how you might define iterate if this comes up frequently for you. Playground

let v = iterate(1, |x| x * 3 + 1).take_while(|x| *x < 1000);

I wouldnâ€™t be surprised if something like that was available in the itertools crate.

EDIT: lol, turns out it already exists!

1 Like

I noticed both your iterate implementation and itertoolsâ€™ implementation use mem::replace. Why is that?

I believe itâ€™s just because mem::replace() skips the need to introduce an intermediate variable when swapping in the next element.

if you want to use kind of functional style, using a sequence with head and tail, please check the crate â€śseqâ€ť https://crates.io/crates/seq
Seq allows you to grow the sequence on Stack while performing recursive function calls.

I choose itertools crate which is just I want, but thank you everyone for shareing your knowledge!