recursion - 为什么使用递归的 Hailstone Sequence 函数仅输出两个值？

Question

我有以下代码:

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;
}

它计算 Hailstone sequence并在 1 处停止。hailSeq(11) 的输出应如下所示:

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

但是，我的输出如下所示:

[11, 34]

我不太确定为什么会发生这种情况。也许 Rust 中的递归存在我不知道的限制，但我确信我的代码中可能只是一个错误。

Answer 1

您的问题不是 Rust 特有的，而是一个更普遍的问题。

在每次调用 hailSeq 时，您每次都会创建一个新的 Vec，因此只有第一个 vec(来自第一次调用)会被使用并返回，因此是 [11, 34] (第三行的 11，第十行的 34)。

要解决此问题，您有两种选择，我将在此处提供一种选择。

第一个是用返回的 vec 扩展当前的 vec，例如myvec.extend_from_slice(&returned_vec)。

第二个解决方案涉及在启动时创建一个 vec 并将相同的实例传递给函数的每次调用。

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 )

作为旁注:如果您知道数字不能为负数，请使用 u32 代替，因为您会在编译时而不是运行时发现错误。