Is it possible to make a recursive closure in Rust?

by

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 fns are no different to those defined at the top level, except they are only accessible within the fn they are defined inside.

More Related Contents:

  1. What does “Overflow evaluating the requirement” mean and how can I fix it?
  2. Way to go from recursion to iteration
  3. Solution for “Fatal error: Maximum function nesting level of ‘100’ reached, aborting!” in PHP
  4. Tower of Hanoi: Recursive Algorithm
  5. Prolog Accumulators. Are they really a “different” concept?
  6. What is recursion and when should I use it?
  7. When does a closure implement Fn, FnMut and FnOnce?
  8. How can I make recursive templates in AngularJS when using nested objects?
  9. Mutably borrow one struct field while borrowing another in a closure
  10. Is Cmake set variable recursive?
  11. Recursive function causing a stack overflow
  12. “application: not a procedure” in binary arithmetic procedures
  13. How do I store a closure in a struct in Rust?
  14. How to declare a higher-ranked lifetime for a closure argument?
  15. count the number of calls of a clause
  16. How do I convert a Rust closure to a C-style callback?
  17. Recursion vs loops
  18. How to use struct self in member method closure
  19. How can I move a captured variable into a closure within a closure?
  20. Can’t borrow mutably within two different closures in the same scope
  21. Real-world examples of recursion [closed]
  22. Can you clone a closure?
  23. How can I modify self in a closure called from a member function?
  24. I got “scheme application not a procedure” in the last recursive calling of a function
  25. Anonymous recursive PHP functions
  26. Implications of foldr vs. foldl (or foldl’)
  27. How does the fibonacci recursive function “work”?
  28. Is there another option to share an Arc in multiple closures besides cloning it before each closure?
  29. How do I pass a closure through raw pointers as an argument to a C function?
  30. SICP recursive process vs iterative process: using a recursive procedure to generate an iterative process

Leave a Comment