È possibile effettuare una chiusura ricorsiva in Rust?

Question

Questo è un esempio molto semplice, ma come vorrei fare qualcosa di simile a:

let fact = |x: u32| { 
    match x { 
     0 => 1, 
     _ => x * fact(x - 1), 
    } 
}; 

So che questo esempio specifico può essere fatto facilmente con l'iterazione, ma mi chiedo se è possibile fare un ricorsiva funzione in Rust per cose più complicate (come attraversare alberi) o se sono invece obbligato a usare il mio stack personale.

Answer 1

Ci sono alcuni modi per farlo.

È possibile inserire chiusure in una struttura e passare questa struttura alla chiusura. È anche possibile definire le strutture in linea in una funzione:

fn main() { 
    struct Fact<'s> { f: &'s Fn(&Fact, u32) -> u32 } 
    let fact = Fact { 
     f: &|fact, x| if x == 0 {1} else {x * (fact.f)(fact, x - 1)} 
    }; 

    println!("{}", (fact.f)(&fact, 5)); 
} 

Questo aggira il problema di avere un tipo infinito (una funzione che si prende come argomento) e il problema che fact non è ancora definita all'interno della chiusura se stesso quando si scrive let fact = |x| {...} e quindi non si può fare riferimento ad esso lì.

Questo funziona in Rust 1.17, ma potrebbe essere reso illegale in futuro in quanto è pericoloso in alcuni casi, come indicato in the blog post The Case of the Recurring Closure. È completamente al sicuro qui poiché non c'è alcuna mutazione però.

---

Un'altra opzione è quella di scrivere solo una funzione ricorsiva come un elemento di fn, che può anche essere definita in linea in una funzione:

fn main() { 
    fn fact(x: u32) -> u32 { if x == 0 {1} else {x * fact(x - 1)} } 

    println!("{}", fact(5)); 
} 

Questo funziona bene se non c'è bisogno di catturare qualsiasi cosa dall'ambiente

---

più Una possibilità è quella di utilizzare la soluzione fn articolo ma esplicitamente passare l'args/ambiente che si desidera.

fn main() { 
    struct FactEnv { base_case: u32 } 
    fn fact(env: &FactEnv, x: u32) -> u32 { 
     if x == 0 {env.base_case} else {x * fact(env, x - 1)} 
    } 

    let env = FactEnv { base_case: 1 }; 
    println!("{}", fact(&env, 5)); 
} 

Tutti questi funzionano con Rust 1.17 e probabilmente hanno funzionato dalla versione 0.6. Gli fn definiti all'interno di fn s non sono diversi da quelli definiti al livello superiore, eccetto che sono accessibili solo all'interno dello fn all'interno.