Можно ли создать рекурсивное замыкание в Rust?

Проблема рекурсивных замыканий в Rust

Действительно, напрямую создать рекурсивное замыкание нельзя из-за особенностей системы владения и замыканий. Замыкание не может ссылаться на себя до завершения инициализации. Однако есть несколько проверенных подходов.

Решение 1: Использование Rc и RefCell (или Cell)

Самый гибкий способ — обернуть замыкание в умный указатель, который позволяет разделять владение:

use std::rc::Rc;
use std::cell::RefCell;

fn main() {
    let factorial: Rc<RefCell<Box<dyn Fn(u32) -> u32>>> = 
        Rc::new(RefCell::new(Box::new(|_| 0))); // временная заглушка

    let factorial_clone = factorial.clone();
    *factorial.borrow_mut() = Box::new(move |n: u32| -> u32 {
        if n <= 1 {
            1
        } else {
            n * factorial_clone.borrow()(n - 1)
        }
    });

    println!("5! = {}", factorial.borrow()(5)); // 120
}

Решение 2: Использование Cell для простых случаев

Если замыкание не захватывает внешние переменные с нетривиальным владением, можно использовать Cell:

use std::cell::Cell;

fn main() {
    let factorial: Cell<Option<Box<dyn Fn(u32) -> u32>>> = Cell::new(None);
    
    let fact = |n: u32| -> u32 {
        let f = factorial.take().unwrap();
        let result = f(n);
        factorial.set(Some(f)); // возвращаем обратно
        result
    };
    
    let real_fact: Box<dyn Fn(u32) -> u32> = Box::new(move |n| {
        if n <= 1 { 1 } else { n * fact(n - 1) }
    });
    
    factorial.set(Some(real_fact));
    println!("5! = {}", factorial.take().unwrap()(5)); // 120
}

Решение 3: Рекурсия через трейт (более идиоматично)

Лучший способ — определить собственный трейт для рекурсивных замыканий:

trait RecursiveFn {
    fn call(&self, n: u32) -> u32;
}

impl<F> RecursiveFn for F where F: Fn(u32, &dyn RecursiveFn) -> u32 {
    fn call(&self, n: u32) -> u32 {
        (self)(n, self)
    }
}

fn main() {
    let factorial = |n: u32, f: &dyn RecursiveFn| -> u32 {
        if n <= 1 { 1 } else { n * f.call(n - 1) }
    };
    
    println!("5! = {}", factorial.call(5)); // 120
}

Важные замечания

• Производительность: Использование Rc и RefCell добавляет накладные расходы. Для критичного кода лучше использовать обычные функции.
• Захват переменных: Решение с Rc/RefCell позволяет замыканию захватывать внешние переменные через move.
• Альтернатива: Если рекурсия глубокая, рассмотрите итеративный подход или использование fn с замыканием через аргумент.

Рекомендую третий подход (с трейтом) — он наиболее элегантный и не требует изменяемой памяти. Но для быстрого прототипирования подойдёт первый вариант.

fn main() {
    let factorial = |n: u32| {
        fn inner(n: u32, f: &dyn Fn(u32) -> u32) -> u32 {
            if n <= 1 { 1 } else { n * f(n - 1) }
        }
        // Используем Y-комбинатор вручную
        let rec = |n| inner(n, &|n| inner(n, &|n| inner(n, &|n| inner(n, &|n| n))));
        rec(n)
    };
    
    println!("5! = {}", factorial(5)); // 120
}

fn main() {
    let factorial: Box<dyn Fn(u32) -> u32> = Box::new(|n| {
        if n <= 1 { 1 } else { n * factorial(n - 1) }
    });
    // Ошибка! factorial ещё не инициализировано.
    // Исправление: используйте unsafe или Cell.
}