recursion - 具有外部变量的递归函数

Question

我在变量作用域方面遇到了一些困难。我目前有这样的代码:

use std::collections::HashMap;

fn main() {
    let mut cache: HashMap<usize, usize> = HashMap::new();

    fn fib(n: usize) -> usize {
        // Special values
        if n == 0 || n == 1 {
            return 1;
        }

        // Check if value is in cache
        if let Some(&a) = cache.get(&n) {
            return a;
        }

        // Calculate
        let f = fib(n - 2) + fib(n - 1);

        // Insert in cache for later use
        cache.insert(n, f);

        return f;
    }

    println!("The 11th Fibonacci number is: {}", fib(10));
}

我想生成斐波那契数列，但也使用缓存来跳过重新计算相同的项目。实际代码做了一些更重的计算，但也使用了递归。

但是，尝试编译它时，我得到一个 can't capture dynamic environment in a fn item;使用 ||在 cache.get 和 cache.insert 处警告 { ... } 闭包形式。将此闭包形式应用于该代码:

use std::collections::HashMap;

fn main() {
    let mut cache: HashMap<usize, usize> = HashMap::new();

    let fib = |n: usize| -> usize {
        // Special values
        if n == 0 || n == 1 {
            return 1;
        }

        // Check if value is in cache
        if let Some(&a) = cache.get(&n) {
            return a;
        }

        // Calculate
        let f = fib(n - 2) + fib(n - 1);

        // Insert in cache for later use
        cache.insert(n, f);

        return f;
    };

    println!("The 11th Fibonacci number is: {}", fib(10));
}

修复了 cache 错误，但在 let f = ... 处给出了 cannot find function `fib` in this scope 警告。

我还尝试使用 Is it possible to make a recursive closure in Rust? 中所述的环境，但我不喜欢我两次调用相同的函数，因此在环境中有一个可变缓存时两次借用环境。

我将如何处理这个奇怪的案例？

Answer 1

您在使用环境方面走在了正确的轨道上，但是您需要确保所有需要可变的东西都是可变的:

use std::collections::HashMap;

fn main() {
    struct FibEnv { cache: HashMap<usize, usize> }

    fn fib(mut env: &mut FibEnv, n: usize) -> usize {
        // Special values
        if n == 0 || n == 1 {
            return 1;
        }

        // Check if value is in cache
        if let Some(&a) = env.cache.get(&n) {
            return a;
        }

        // Calculate
        let f = fib(&mut env, n - 2) + fib(&mut env, n - 1);

        // Insert in cache for later use
        env.cache.insert(n, f);

        return f;
    }

    let cache: HashMap<usize, usize> = HashMap::new();
    let mut env = FibEnv { cache: cache };
    println!("The 11th Fibonacci number is: {}", fib(&mut env, 10));
}

---

正如@Shepmaster 在评论中所述，以下更简单:

use std::collections::HashMap;

fn main() {
    fn fib(cache: &mut HashMap<usize, usize>, n: usize) -> usize {
        // Special values
        if n == 0 || n == 1 {
            return 1;
        }

        // Check if value is in cache
        if let Some(&a) = cache.get(&n) {
            return a;
        }

        // Calculate
        let f = fib(cache, n - 2) + fib(cache, n - 1);

        // Insert in cache for later use
        cache.insert(n, f);

        return f;
    }

    let mut cache: HashMap<usize, usize> = HashMap::new();
    println!("The 11th Fibonacci number is: {}", fib(&mut cache, 10));
}