recursion - 是否可以在 Rust 中进行递归闭包？

Question

这是一个非常简单的示例，但我将如何做类似以下的事情:

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

我知道这个具体示例可以通过迭代轻松完成，但我想知道是否可以在 Rust 中为更复杂的事情(例如遍历树)创建递归函数，或者我是否需要使用我的自己的堆栈。

Answer 1

有几种方法可以做到这一点。

您可以将闭包放入结构中并将该结构传递给闭包。您甚至可以在函数中定义内联结构:

fn main() {
    struct Fact<'s> { f: &'s dyn 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 尚未在闭包本身内部定义的问题让事实=|x| {...} 所以不能在那里引用它。

---

另一种选择是将递归函数编写为 fn 项，也可以在函数中内联定义:

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

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

如果您不需要从环境中捕获任何东西，这就可以正常工作。

---

另一种选择是使用 fn 项目解决方案，但显式传递您想要的 args/environment。

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 中访问它们是定义在里面。