Это очень простой пример, но как мне сделать что-то похожее на:
let fact = |x: u32| {
match x {
0 => 1,
_ => x * fact(x - 1),
}
};
Я знаю, что этот конкретный пример можно легко сделать с помощью итерации, но мне интересно, можно ли сделать рекурсивную функцию в Rust для более сложных вещей (например, пересечение деревьев) или если я должен использовать мой собственный стек.
Есть несколько способов сделать это.
Вы можете поместить замыкания в структуру и передать эту структуру замыканию. Вы даже можете определить структуры, встроенные в функцию:
fn main() {
struct Fact<'s> { f: & 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| {...} let fact = |x| {...} и поэтому там нельзя ссылаться на это.
Это работает в Rust 1.17, но, возможно, в будущем станет незаконным, поскольку в некоторых случаях это опасно, как об этом говорится в сообщении в блоге "Случай повторяющегося закрытия". Здесь совершенно безопасно, поскольку мутации нет.
Другой вариант - просто написать рекурсивную функцию как элемент fn, который также может быть определен внутри функции:
fn main() {
fn fact(x: u32) -> u32 { if x == 0 {1} else {x * fact(x - 1)} }
println!("{}", fact(5));
}
Это прекрасно работает, если вам не нужно захватывать что-либо из окружающей среды.
Еще один вариант - использовать решение fn item, но явно передать нужные аргументы 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 они определены.
Вот действительно уродливое и многословное решение, которое я придумал:
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...>), и оно все еще работает.