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编写时尚未在闭包本身内部定义的问题，因此无法在其中let fact = |x| {...}引用它。

---

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

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

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

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

---

另一种选择是使用fn项目解决方案，但明确传递您想要的参数/环境。

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 版本开始就可以使用。s 内部定义的fn'sfn与顶层定义的没有什么不同，除了它们只能在fn它们定义的内部访问。

Answer 2

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

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...>）并且它仍然有效。