Rust递归传递迭代器触发递归限制错误求助

函数声明 #

原函数定义如下：

fn find_solutions_internal<'a, I>(&self, words: I, iterate_from: usize, chain: &mut Vec<u32>)
    where I: Iterator<Item=&'a u32> + Clone;

问题背景 #

该函数会以不同过滤器递归遍历同一向量（最大递归深度为5），原本认为传递迭代器作为参数能提升效率，但实际编写的代码触发了编译错误。

触发错误的代码片段 #

let iterator = words.skip(iterate_from).filter(|&mask| mask & last_mask == 0);
let filtered_words = iterator.clone();

iterator.enumerate().for_each(|(i, &mask)| {
    chain.push(mask);
    self.find_solutions_internal(filtered_words.clone(), i, chain); // filtered_words.clone()间接引发错误
    chain.pop();
});

编译错误信息 #

error: reached the recursion limit while instantiating `<std::iter::Filter<std::iter::Sk...]>::{closure#0}]>::{closure#0}]>`
115 |         self.iter.fold(init, fold)
    |         ^^^^^^^^^^^^^^^^^^^^^^^^^^
    |
note: `<std::iter::Filter<I, P> as Iterator>::fold` defined here
...

问题原因 #

Rust的类型系统会为每个嵌套的迭代器组合（比如Filter<Skip<I>, _>）生成唯一的具体类型。每次递归调用时，传递的迭代器类型会多一层嵌套，随着递归深度增加，类型的嵌套层级会迅速膨胀，最终触发编译器的递归实例化限制——哪怕实际运行时递归深度只有5，编译器在处理类型推导时也会提前达到阈值。

解决方案 #

方案1：类型擦除（Box化迭代器） #

通过Box<dyn Iterator>将迭代器装箱，统一类型，避免嵌套类型的无限膨胀。修改函数声明和调用代码：

修改后的函数声明与实现：

fn find_solutions_internal<'a>(&self, words: Box<dyn Iterator<Item=&'a u32> + 'a>, iterate_from: usize, chain: &mut Vec<u32>) {
    let last_mask = chain.last().copied().unwrap_or(0);
    let iterator = words.skip(iterate_from).filter(|&mask| mask & last_mask == 0);
    let filtered_words = Box::new(iterator.clone());

    iterator.enumerate().for_each(|(i, &mask)| {
        chain.push(mask);
        self.find_solutions_internal(Box::new(filtered_words.clone()), i, chain);
        chain.pop();
    });
}

这种方式会带来极小的运行时开销，但对于深度仅为5的递归场景，完全可以忽略。

方案2：提前收集到向量 #

将迭代器的结果提前收集到向量中，后续递归传递向量的切片或迭代器——此时迭代器类型始终是std::slice::Iter<'a, u32>，不会产生嵌套类型问题，代码也更简洁：

修改后的函数声明与实现：

fn find_solutions_internal<'a>(&self, words: &'a [u32], iterate_from: usize, chain: &mut Vec<u32>) {
    let last_mask = chain.last().copied().unwrap_or(0);
    // 提前过滤并收集到向量
    let filtered_words: Vec<_> = words
        .iter()
        .skip(iterate_from)
        .filter(|&mask| mask & last_mask == 0)
        .cloned()
        .collect();

    filtered_words.iter().enumerate().for_each(|(i, &mask)| {
        chain.push(mask);
        self.find_solutions_internal(&filtered_words, i, chain);
        chain.pop();
    });
}

这种方式会有一次收集向量的开销，但对于递归深度浅的场景，性能影响微乎其微，同时避免了类型相关的编译问题。

总结 #

如果追求极致效率且能接受极小的类型擦除开销，选择Box化迭代器方案；如果优先保证代码简洁、避免编译问题，提前收集到向量是更稳妥的选择。

内容的提问来源于stack exchange，提问作者mozkomor05