Crate recur_fn

A library that provides you a more flexible way to construct and extend the recursive function.

The RecurFn trait provides a recursive function abstraction that the recursion can be customized.

It means that you can construct anonymous recursive function,

use recur_fn::{recur_fn, RecurFn};

let fib = recur_fn(|fib, n: u64| {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
});

assert_eq!(55, fib.call(10));

and you can extends the body of the recursive function.

use recur_fn::{recur_fn, RecurFn};
use std::cell::RefCell;

let fib = recur_fn(|fib, n: u64| {
    if n <= 1 {
        n
    } else {
        fib(n - 1) + fib(n - 2)
    }
});

let log = RefCell::new(Vec::new());

let fib_with_logging = recur_fn(|recur, n: u64| {
    log.borrow_mut().push(n);
    fib.body(recur, n)
});

fib_with_logging.call(3);
assert_eq!(*log.borrow(), vec![3, 2, 1, 0, 1]);

As recur_fn is a convenient way to construct RecurFn, it comes with cost. You can define a struct and implement RecurFn trait to make it zero-cost,

use recur_fn::RecurFn;

let fib = {
    struct Fib {}
    impl RecurFn<u64, u64> for Fib {
        // It's highly recommended to mark `body` method as `#[inline]`,
        // otherwise, calling it would not be faster than using `recur_fn`,
        // which is against the purpose of implementing `RecurFn` manually.
        #[inline]
        fn body(&self, fib: impl Fn(u64) -> u64, n: u64) -> u64 {
            if n <= 1 {
                n
            } else {
                fib(n - 1) + fib(n - 2)
            }
        }
    }
    Fib {}
};

assert_eq!(55, fib.call(10));

or if the function doesn't need to capture anything, you can use as_recur_fn macro.

use recur_fn::{as_recur_fn, RecurFn};

let fact = as_recur_fn!(fact(n: u64) -> u64 {
    if n == 0 { 1 } else { n * fact(n - 1) }
});
assert_eq!(6, fact.call(3));
assert_eq!(0,
    fact.body(|_| 0, 3));

DynRecurFn is a dynamic version that allows to have a trait object.

use recur_fn::{recur_fn, RecurFn, DynRecurFn};

let dyn_fact: &DynRecurFn<_, _> = &recur_fn(|fact, n: u64| {
    if n == 0 { 1 } else { n * fact(n - 1) }
});
assert_eq!(3, dyn_fact.dyn_body(&|_| 1, 3));
assert_eq!(3, dyn_fact.body(&|_| 1, 3));

// `&dyn DynRecurFn` implements `RecurFn`.
fn test_fact(fact: impl RecurFn<u64, u64>) {
    assert_eq!(6, fact.call(3));
    assert_eq!(0, fact.body(|_| 0, 3));
}
test_fact(dyn_fact);

Macros

as_recur_fn

Constructs a zero-cost RecurFn implementation that doesn't capture.

Traits

DynRecurFn	The more dynamic RecurFn trait that supports trait object.
RecurFn	The recursive function trait.

Functions

recur_fn

Constructs a RecurFn by providing a closure as body. This is the most convenient to construct an anonymous RecurFn.