Rust中自引用递归函数结果缓存的实现问题（欧拉项目第76题）

问题背景 #

我正在通过欧拉项目第76题自学Rust，最初写出递归解法，但因重复计算相同输入导致运行极慢。尝试用HashMap实现缓存优化时，遇到了借用检查器（borrow checker）的错误。

初始递归代码 #

fn main() {
    println!("{}", solution(100, 99));
}

fn solution(sum_to: i32, max_size: i32) -> i32 {
    if sum_to == 0 || max_size == 1 {
        1
    } else if sum_to < 0 {
        0
    } else {
        (1..=max_size)
            .map(|i| solution(sum_to - i, min(i, sum_to - i)))
            .sum()
    }
}

尝试的缓存实现代码 #

use std::cmp::min;
use std::collections::HashMap;

fn main() {
    println!("{}", solution_head(100))
}

fn solution_head(sum_to: i32) -> i32 {
    let mut cache = HashMap::new();
    (1..sum_to)
        .map(|i| solution(&mut cache, sum_to - i, min(i, sum_to - i)))
        .sum()
}

fn solution(
    cache: &mut HashMap<i32, HashMap<i32, i32>>,
    sum_to: i32,
    max_size: i32,
) -> i32 {
    if sum_to == 0 {
        1
    } else if sum_to < 0 {
        0
    } else {
        let cache_entry = cache.entry(sum_to);
        let map = cache_entry.or_insert(HashMap::new());
        let map_entry = map.entry(max_size);
        *map_entry.or_insert_with(|| {
            (1..=max_size)
                .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
                .sum()
        })
    }
}

错误信息 #

error[E0500]: closure requires unique access to `*cache` but it is already borrowed
  --> src/bin/problem_76.rs:27:35
   |
24 |         let cache_entry = cache.entry(sum_to);
   |                           ------------------- borrow occurs here
...
27 |         *map_entry.or_insert_with(|| {
   |                    -------------- ^^ closure construction occurs here
   |                    |
   |                    first borrow later used by call
28 |             (1..=max_size)
29 |                 .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
   |                                   ----- second borrow occurs due to use of `*cache` in closure

核心问题 #

代码中通过cache.entry(sum_to)获取Entry时，已经持有了cache的可变借用；而在or_insert_with的闭包里递归调用solution时，又需要再次借用cache，这违反了Rust的可变借用规则：同一时间只能有一个可变引用。

正确的惯用实现方式 #

解决思路是将缓存的读取与写入操作分开：先尝试从缓存中查询结果，若不存在则计算，最后将计算结果插入缓存。这样就不会在持有Entry借用的同时进行递归调用，避免了借用冲突。

修改后的完整代码如下：

use std::cmp::min;
use std::collections::HashMap;

fn main() {
    println!("{}", solution_head(100))
}

fn solution_head(sum_to: i32) -> i32 {
    let mut cache = HashMap::new();
    (1..sum_to)
        .map(|i| solution(&mut cache, sum_to - i, min(i, sum_to - i)))
        .sum()
}

fn solution(
    cache: &mut HashMap<i32, HashMap<i32, i32>>,
    sum_to: i32,
    max_size: i32,
) -> i32 {
    if sum_to == 0 {
        return 1;
    }
    if sum_to < 0 {
        return 0;
    }

    // 优先从缓存读取结果，避免重复计算
    if let Some(sub_cache) = cache.get(&sum_to) {
        if let Some(&result) = sub_cache.get(&max_size) {
            return result;
        }
    }

    // 缓存未命中，递归计算结果
    let result = (1..=max_size)
        .map(|i| solution(cache, sum_to - i, min(i, sum_to - i)))
        .sum();

    // 将结果写入缓存，供后续调用使用
    cache.entry(sum_to)
        .or_insert_with(HashMap::new)
        .insert(max_size, result);

    result
}

关键说明 #

1. 先查缓存：通过cache.get和sub_cache.get进行不可变查询，此时的不可变借用会在查询结束后立即释放，不会影响后续的递归调用。
2. 后写缓存：计算完成后，再通过entry API将结果插入缓存，这时候递归调用已经完成，不会出现借用冲突。

这种写法既符合Rust的借用规则，又实现了缓存优化的目的，是处理递归缓存场景的惯用方式。

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