是否可以在Rust中進行遞歸封閉？

Question

這是一個非常簡單的例子，但我會怎麼做類似的東西：

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

我知道這個具體的例子可以用迭代很容易做到，但我不知道是否有可能作出遞歸在Rust中用於更復雜的事情（比如遍歷樹）或者我需要使用自己的堆棧。

Answer 1

有幾種方法可以做到這一點。

您可以將閉包放入一個結構中並將此結構傳遞給閉包。你甚至可以在一個函數定義結構內聯：

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

這不需要是fact尚未關閉內部定義的無限類型（即需要自身作爲參數的函數），問題的問題本身當寫let fact = |x| {...}，所以不能在那裏引用它。

這適用於Rust 1.17，但可能在將來會被認定爲非法，因爲在某些情況下它很危險，如the blog post The Case of the Recurring Closure中所述。這裏完全安全，因爲沒有突變。

---

另一種選擇是隻寫一個遞歸函數作爲fn項，也可以在一個內聯函數定義：

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

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

這工作得很好，如果你不需要捕獲任何來自環境。

---

還有一個選擇是使用fn項目解決方案，但明確地傳遞你想要的ARGS /環境。

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

所有這些工作與Rust 1.17，並可能從0.6版起工作。在fn中定義的fn與在頂層定義的fn相同，區別僅在於它們在裏面定義的fn之內。