此crate为Rust中的递归提供了某些功能。

动机

大多数迭代问题都可以用递归而不是循环来解决。事实上，当你开始学习函数式编程时，你会发现使用递归解决给定问题的可能性。如果语言不优化某些类型的递归，编程函数式可能很困难，因为如果发生大的递归情况，最终可能会发生栈溢出。

一种常见的优化是所谓的“尾调用优化”、“尾调用归约”或任何类似的名称。首先，让我们了解尾调用。尾调用基本上是在函数体“尾部”找到的函数。尾位置意味着调用是函数体中最后完成的事情。优化它意味着，编译器不会为被调用函数生成新的堆栈帧，而是将重用当前帧。实际上，调用可能被转换成一个循环。但是，它仍然是递归，因为程序员没有编写循环。这只是优化。

目前，Rust没有提供任何语言项来优化尾调用。有一个“承诺”的特性名为become。 become目前只是一个保留的标识符，但意图是它像一个返回一样，但是执行尾调用归约。好吧，目前还没有关于何时实现或是否将实现它的预期。因此，我们决定创建一个库，允许程序员编写带有尾调用的优化递归。

示例

看看这个阶乘函数

fn fac(n: u128) -> u128 {
    if n > 1 {
        n * fac(n - 1)
    } else {
        n
    }
}

很明显，上面的函数不是尾递归。在递归调用之后，我们仍然需要将结果乘以n。然而，这个函数有一个众所周知的版本，它接受一个额外的参数：累加器。看看

fn fac(n: u128) -> u128 {
    //!
    fn fac_with_acc(n: u128, acc: u128) -> u128 {
        if n > 1 {
            fac_with_acc(n - 1, acc * n)
        } else {
            1
        }
    }

    fac_with_acc(n, 1)
}

fac_with_acc函数是尾递归的。在调用自己之后没有其他工作要做。只有一个问题：Rust还没有进行任何尾调用优化。现在，crate tramp完成了它的任务。我们在该crate中实现了一个跳板。跳板通过调用一个可能返回另一个函数（将被再次调用）或计算结果的函数来模拟尾调用优化。跳板将循环调用返回的函数，每当函数返回一个计算值而不是一个函数时，跳板返回该值。请看下面的示例。

#[macro_use] extern crate tramp;

use tramp::{tramp, Rec};

fn factorial(n: u128) -> u128 {
    fn fac_with_acc(n: u128, acc: u128) -> Rec<u128> {
        if n > 1 {
            rec_call!(fac_with_acc(n - 1, acc * n))
        } else {
            rec_ret!(acc)
        }
    }

    tramp(fac_with_acc(n, 1))
}

assert_eq!(factorial(5), 120);