是否可以在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 Remedring Closure所述.这里完全安全,因为没有突变.

另一种选择是将递归函数编写为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内部定义的fns为无来者在顶层定义不同,但它们仅在访问fn他们的内部规定.

Answer 2

截至 Rust 1.62（2022 年 7 月），仍然没有直接的方法在闭包中递归。正如其他答案所指出的，您至少需要一些间接，例如将闭包作为参数传递给自身，或者在创建闭包后将其移动到单元格中。这些东西可以工作，但在我看来它们有点恶心，而且对于 Rust 初学者来说它们绝对很难遵循。如果您想使用递归但必须有一个闭包，例如因为您需要实现FnOnce()使用 with的东西thread::spawn，那么我认为最干净的方法是对递归部分使用常规fn函数并将其包装在非捕获环境的递归闭包。这是一个例子：

let x = 5;
let fact = || {
    fn helper(arg: u64) -> u64 {
        match arg {
            0 => 1,
            _ => arg * helper(arg - 1),
        }
    }
    helper(x)
};
assert_eq!(120, fact());

Answer 3

这是我想出的一个非常丑陋且冗长的解决方案：

use std::{
    cell::RefCell,
    rc::{Rc, Weak},
};

fn main() {
    let weak_holder: Rc<RefCell<Weak<dyn Fn(u32) -> u32>>> =
        Rc::new(RefCell::new(Weak::<fn(u32) -> u32>::new()));
    let weak_holder2 = weak_holder.clone();
    let fact: Rc<dyn Fn(u32) -> u32> = Rc::new(move |x| {
        let fact = weak_holder2.borrow().upgrade().unwrap();
        if x == 0 {
            1
        } else {
            x * fact(x - 1)
        }
    });
    weak_holder.replace(Rc::downgrade(&fact));

    println!("{}", fact(5)); // prints "120"
    println!("{}", fact(6)); // prints "720"
}

这样做的优点是您可以使用预期的签名调用函数（不需要额外的参数），它是一个可以捕获变量（通过移动）的闭包，它不需要定义任何新的结构，并且闭包可以从函数或以其他方式存储在超出其创建范围（作为 ）的位置，Rc<Fn...>但它仍然有效。