Why does my Hailstone Sequence function using recursion only output two values?

Question

I have the following code:

fn hailSeq(number: i32) -> Vec<i32> {
    let mut vec = Vec::new();
    vec.push(number);
    if number == 1 {
        vec.push(1);
        return vec;
    }
    if number % 2 == 0 {
        let num = number / 2;
        vec.push(num);
        hailSeq(num);
    } else {
        let num = 3 * number + 1;
        vec.push(num);
        hailSeq(num);
    }
    return vec;
}

It calculates the Hailstone sequence and stops at 1. The output should look like this for hailSeq(11):

[11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

However, my output looks like this:

[11, 34]

I am not really sure why this is occurring. Perhaps there is a limit on recursion in Rust that I don't know about, but I'm sure there's probably just an error in my code.

Please use `rustfmt` to format your code properly next time. Second, in rust we do not use camelCase, but snake_case, e.g. your function name should be hail_seq. Third, don't use an explicit `return` for the last statement, that is very unrusty. Just write `vec` (withouth return and `;`) — hellow, Nov 09 '18 at 12:51
The more idiomatic in Rust is to [use an iterator](https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=7ddbd3323cc319175982ef50bc2955c5). — Boiethios, Nov 09 '18 at 13:10
The fun is there is an implementation for Rust on the link that I added https://rosettacode.org/wiki/Hailstone_sequence#Rust ;) — Stargateur, Nov 09 '18 at 13:10

score 3 · Accepted Answer · edited Nov 09 '18 at 15:00

Your problem is not Rust-specific, but a more general problem.

On every call of hailSeq you create a new Vec every time, so that only the first vec (from the first call) would be used and returned, hence the [11, 34] (11 from the third line, 34 from the tenth line).

To fix this you have two options, I will provide one here.

The first one would be to extend the current vec with the returned vec, e.g. myvec.extend_from_slice(&returned_vec).

The second solution involves creating a vec on startup and passing the same instance to every call of the function.

fn hail_seq(number: i32) -> Vec<i32> {
    fn inner(number: i32, vec: &mut Vec<i32>) {
        vec.push(number);
        if number == 1 {
            return;
        }
        if number % 2 == 0 {
            let num = number / 2;
            inner(num, vec);
        } else {
            let num = 3 * number + 1;
            inner(num, vec);
        }   
    }
    let mut v = vec![];
    inner(number, &mut v);
    v
}

fn main() {
    println!("{:?}", hail_seq(11));
}

(playground)

As a side-note: If you know that a number can't be negative, use a u32 instead because you will find errors at compile time instead of runtime.

Why does my Hailstone Sequence function using recursion only output two values?

1 Answers1