Is it possible to make a recursive closure in Rust?
Solution 1
There are a few ways to do this.
You can put closures into a struct and pass this struct to the closure. You can even define structs inline in a function:
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));
}
This gets around the problem of having an infinite type (a function that takes itself as an argument) and the problem that fact
isn't yet defined inside the closure itself when one writes let fact = |x| {...}
and so one can't refer to it there.
Another option is to just write a recursive function as a fn
item, which can also be defined inline in a function:
fn main() {
fn fact(x: u32) -> u32 { if x == 0 {1} else {x * fact(x - 1)} }
println!("{}", fact(5));
}
This works fine if you don't need to capture anything from the environment.
One more option is to use the fn
item solution but explicitly pass the args/environment you want.
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));
}
All of these work with Rust 1.17 and have probably worked since version 0.6. The fn
's defined inside fn
s are no different to those defined at the top level, except they are only accessible within the fn
they are defined inside.
Solution 2
Here's a really ugly and verbose solution I came up with:
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"
}
The advantages of this are that you call the function with the expected signature (no extra arguments needed), it's a closure that can capture variables (by move), it doesn't require defining any new structs, and the closure can be returned from the function or otherwise stored in a place that outlives the scope where it was created (as an Rc<Fn...>
) and it still works.
Undeterminant
Updated on June 09, 2022Comments
-
Undeterminant almost 2 years
This is a very simple example, but how would I do something similar to:
let fact = |x: u32| { match x { 0 => 1, _ => x * fact(x - 1), } };
I know that this specific example can be easily done with iteration, but I'm wondering if it's possible to make a recursive function in Rust for more complicated things (such as traversing trees) or if I'm required to use my own stack instead.
-
Brian Campbell almost 6 yearsIs it actually the case that this may be disallowed in the future? As far as I can tell, this is safe because we're using
Fn
, so we have no mutable aliasing, and if you tried to write something recursive usingFnMut
the borrow checker would complain because of the multiple borrows of the&mut FnMut()
reference. That blog post was written against a very old version of Rust, and it looks like it's solved by the newerFn
/FnMut
/FnOnce
traits, where previously&fn
was actually mutable. -
Andrew about 3 yearsCouldn't this ugliness be avoided if local functions simply captured their context like in most functional languages and then you could define a function instead of using the ugly closure syntax with the obvious problem for recursion ? Why does Rust have this apparently pointless and limiting difference in the way that it treats functions and closures ?
-
huon about 3 years@Andrew I think a major part is historical reasons, and that closures are harder without a garbage collector, because the context cannot just be freely captured (via the heap). Rust went through a few iterations of how closures worked before it reached the current one. They are slowly converging (e.g. closures without captures can be coerced to a
fn(...) -> ...
function pointer value), but yet not allowing closures to be declared withfn
. FWIW, this isn't entirely simple, for instance, it would require syntax likemove fn foo(...)
to control how values are captured. -
Andrew almost 3 years@huon thanks for the detailed answer, I hadn't considered how Rust's ownership model really complicates the apparently simply.