#recursive #recursion #recur

recur-fn

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

9 releases (5 stable)

2.2.0 Jan 11, 2020
2.1.0 Aug 14, 2019
2.0.0 Apr 17, 2019
1.2.1 Mar 30, 2019
0.3.0 Feb 8, 2019

#1031 in Rust patterns

Download history 111/week @ 2023-10-14 116/week @ 2023-10-21 123/week @ 2023-10-28 137/week @ 2023-11-04 85/week @ 2023-11-11 118/week @ 2023-11-18 127/week @ 2023-11-25 236/week @ 2023-12-02 302/week @ 2023-12-09 235/week @ 2023-12-16 164/week @ 2023-12-23 159/week @ 2023-12-30 290/week @ 2024-01-06 236/week @ 2024-01-13 287/week @ 2024-01-20 337/week @ 2024-01-27

1,170 downloads per month
Used in 3 crates (2 directly)

MIT/Apache

12KB
147 lines

RecurFn

Build Status

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

Documentation: API reference.

Usage

Add this to your Cargo.toml:

[dependencies]
recur-fn = "2.2"

lib.rs:

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

The RecurFn trait is an abstraction of a recursive function. By accepting a function parameter recur as the recursion rather than recurring directly, it makes constructing an anonymous recursive function possible.

use recur_fn::{recur_fn, RecurFn};

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

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

Beside, it makes extending the body of a recursive function possible.

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

let fib = recur_fn(|fib, n: i32| {
    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: i32| {
    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 a RecurFn, calling it is slower than direct recursion. To make it zero-cost, consider defining a struct, implementing RecurFn trait for it and mark the body method by #[inline].

use recur_fn::RecurFn;

let fib = {
    struct Fib {}
    impl RecurFn<i32, i32> for Fib {
        #[inline]
        fn body(&self, fib: impl Fn(i32) -> i32, n: i32) -> i32 {
            if n <= 1 {
                n
            } else {
                fib(n - 1) + fib(n - 2)
            }
        }
    }
    Fib {}
};

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

or if the function doesn't capture anything, you can use recur_fn macro.

use recur_fn::{recur_fn, RecurFn};

let fact = recur_fn!(fact(n: i32) -> i32 {
    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 of RecurFn that allows you to have a trait object.

use recur_fn::{recur_fn, RecurFn, DynRecurFn};
use core::ops::Deref;

let dyn_fact: &dyn DynRecurFn<_, _> =
    &recur_fn(|fact, n: i32| if n == 0 { 1 } else { n * fact(n - 1) });

No runtime deps