Рекурсивная функция с внешней переменной

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

Я хочу, чтобы генерировать числа Фибоначчи, но и использовать кэш, чтобы пропустить пересчитывая одни и те же элементы. Фактический код делает более тяжелый расчет, но также использует рекурсию.

Однако, пытаясь скомпилировать это, я получаю предупреждениена 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, но дает cannot find function `fib` in this scope предупреждение в let f = ....

Я также попытался использовать среду, указанную в 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)); 
}