在Rust中是否可能创建一个递归闭包？

Question

这是一个非常简单的例子，但我该如何做类似于以下内容的事情：

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

我知道这个具体的例子可以轻松通过迭代完成，但我想知道是否有可能在 Rust 中编写递归函数来处理更复杂的事情（比如遍历树），或者我必须使用自己的堆栈。

- Undeterminant

---

Niko Matsakis写了一篇精彩的文章，介绍了如何在当前环境中潜在地（滥用）使用闭包递归以及为什么这肯定会被删除（如果它还没有在incoming中）。当然，您始终可以定义一个调用自身的函数，但它不会捕获外部变量。 - user324242

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

这样可以解决存在无限类型（一个接受自己作为参数的函数）和问题，即当写下let fact = |x| {...}时，在闭包内部fact尚未定义，因此无法在那里引用它。

---

另一种选择是将递归函数编写为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以来可能一直有效。在fn内部定义的fn与在顶层定义的fn没有区别，不同之处在于它们只能在定义它们的fn内部访问。

- huon

---

这种情况将来可能会被禁止吗？据我所知，由于我们正在使用Fn，所以这是安全的，因此我们没有可变别名，如果您尝试使用FnMut编写递归内容，则借用检查器会因&mut FnMut()引用的多个借用而发出警告。该博客文章针对非常旧版本的Rust编写，看起来新的Fn/FnMut/FnOnce特征已经解决了这个问题，之前的&fn实际上是可变的。 - Brian Campbell

如果本地函数像大多数函数式语言一样捕获它们的上下文，那么是否可以避免这种丑陋的情况，然后您可以定义一个函数而不是使用明显递归问题的丑陋闭包语法？为什么Rust在处理函数和闭包的方式上有这种明显无意义和限制性的差异？ - Andrew

@Andrew 我认为主要原因是历史原因，没有垃圾回收器闭包会更难，因为上下文不能自由地通过堆捕获。Rust 在闭包的工作方式上经历了几次迭代才达到当前的状态。它们正在慢慢趋同（例如，没有捕获的闭包可以强制转换为 fn(...) -> ... 函数指针值），但仍不允许使用 fn 声明闭包。顺便说一句，这并不完全简单，例如，它需要像 move fn foo(...) 这样的语法来控制如何捕获值。 - huon

@huon 感谢您详细的回答，我之前没有考虑到 Rust 的所有权模型会让这个看似简单的问题变得复杂。 - Andrew

Answer 2

截至Rust 1.62（2022年7月），在闭包中仍然没有直接递归的方式。如其他答案所指出的那样，您需要至少有一点间接性，例如将闭包作为参数传递给自身，或在创建后将其移入单元格中。这些方法可以工作，但我认为它们有点丑陋，并且对于Rust初学者来说肯定很难跟上。如果你想使用递归但是必须要用到闭包，例如因为你需要实现FnOnce()以便与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());

- Jack O'Connor

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...>），仍然可以正常工作。

- newacct

Answer 4

闭包只是一个带有附加上下文的结构体。因此，您可以这样做来实现递归（假设您想使用递归可变总和来计算阶乘）：

#[derive(Default)]
struct Fact {
    ans: i32,
}

impl Fact {
    fn call(&mut self, n: i32) -> i32 {
        if n == 0 {
            self.ans = 1;
            return 1;
        }
        self.call(n - 1);
        self.ans *= n;
        self.ans
    }
}

使用此结构体，只需：

let mut fact = Fact::default();
let ans = fact.call(5);

- Ireina

Answer 5

似乎有一个导出宏的容器可以更清晰地处理这个问题。

    use fix_fn::fix_fn;

    let fact = fix_fn!(|fact, x: u32| -> u32 {
        if x == 0 {
            1
        } else {
            x * fact(x - 1)
        }
    });

    assert_eq!(fact(5), 120);
    assert_eq!(fact(6), 720);

它还支持move ||闭包。

- Fábio Santos