How to implement Landin's Knot in Rust with closures?

Landin’s knot is a trick for implementing recursion without the need to be able to reference a function’s own name (useful if a language does not natively support recursion).

In pseudo-code, we can create a function "f" that recursively calls itself as follows:

let id = (x) => x    // create a temporary function
let r = id           // store the function in a reference
let f = (n) => !r(n) // create f, a function that unwraps the reference and calls it
r = f                // reassign r to f
f(0)                 // f achieves recursion

The above example would loop forever / cause a stack overflow, but the definition of f could be trivially adjusted to include base cases or calculate fibonacci instead etc.

I tried the naive approach below, but I could not get it working due to compilation errors:

trait I32Fn {
    fn call(&mut self, x: i32) -> i32;
}

struct Closure {
    f: Box<dyn FnMut(i32) -> i32>,
}

impl I32Fn for Closure {
    fn call(&mut self, x: i32) -> i32 {
        (self.f)(x)
    }
}

fn main() {
    let id: Box<dyn I32Fn> = Box::new(Closure { f: Box::new(|x| x) });
    let mut r = id;
    let mut f: Box<dyn I32Fn> = Box::new(Closure {
        f: Box::new(|n: i32| -> i32 { (*r).call(n) }),
    });
    *r = *f;
    println!("{}", (*f).call(0));
}

Presumably if we store closures on the heap in some orderly way (in an arena perhaps) then there should be some way to safely allow a closure to refer to itself?

>Solution :

This step:

r = f                // reassign r to f

Is in fundamental contradiction with Rust’s rules: f holds a reference to r yet we assign it (we broke aliasable xor mutable).

But there is a solution to that: interior mutability.

Also this:

f(0)                 // f achieves recursion

Is quite a problem since we moved f in the previous step. But again, there are solutions to that: for example, reference counting.

All in all:

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

fn main() {
    let id: Rc<RefCell<Rc<dyn Fn(i32) -> i32>>> = Rc::new(RefCell::new(Rc::new(|x| x)));
    let mut r = id;
    let f: Rc<dyn Fn(i32) -> i32> = Rc::new({
        let r = Rc::clone(&r);
        move |n| {
            dbg!(n);
            r.borrow()(n + 1)
        }
    });
    *r.borrow_mut() = Rc::clone(&f);
    f(0);
}

Playground.