Decurse

示例

#[decurse::decurse] // 👈 Slap this on your recursive function and stop worrying about stack overflow!
fn factorial(x: u32) -> u32 {
	if x == 0 {
		1
	} else {
		x * factorial(x - 1)
	}
}

println!("{}", factorial(10));

更多示例（斐波那契、DFS 等）在 示例目录 中。

功能

此包提供的宏使您的递归函数在堆上运行。在稳定 Rust（1.56 时）上工作。

以下是一个示例，以说明机制。

fn factorial(x: u32) -> u32 {
	// 🅐
	if x == 0 {
		1
	} else {
		
		let rec = {
			// 🅑
			factorial(x - 1)
		};

		// 🅒
		rec * x
	}
}

如果我们调用 factorial(1)，以下将发生：

• 我们在函数中从点 🅐 开始运行代码。
• 当我们到达点 🅑 时，我们不会立即调用 factorial(0)，而是保存需要调用 factorial(0) 的信息¹。
• 一旦保存了这些信息，我们就 暂停 factorial(1) 的执行，将状态存储在堆上²。
• 然后我们执行 factorial(0)。在此期间，factorial(1) 的“栈状态”不在栈上。它存储在堆上。
• 一旦我们得到 factorial(0) 的结果，我们 恢复 factorial(1)，并给它 factorial(0) 的结果³。
• 执行从点 🅒 继续进行。

¹ 要将此信息发送到函数外部，我们将它放入线程本地。

² 这是通过将您的函数转换为异步函数并等待暂停来实现的。这是一种使用异步/等待的变通方法。

³ 这再次使用线程本地。

fn factorial(arg_0: u32) -> u32 {
	async fn factorial(x: u32) -> u32 {
		if x == 0 {
			1
		} else {
			x * ({
				// Save what we have to do next.
				::decurse::for_macro_only::sound::set_next(factorial(x - 1));
				// Pause the current function.
				::decurse::for_macro_only::sound::PendOnce::new().await;
				// Once resumed, get the result.
				::decurse::for_macro_only::sound::get_result(factorial)
			})
		}
	}
	::decurse::for_macro_only::sound::execute(factorial(arg_0))
}

用法

此crate提供了两个宏：decurse和decurse_unsound。简单来说，只需将它们放在函数顶部即可。

#[decurse::decurse]
fn some_function(...) -> ...

#[decurse::decurse_unsound]
fn some_function(...) -> ...

decurse

这是你应该优先选择的版本。它不使用不安全代码，因此是安全的。

然而，它不适用于具有生命周期类型（如&T，SomeStruct<'a>等）的参数或返回类型的函数。

decurse_unsound

此宏以非常危险的方式使用不安全代码。我远未确信它是安全的，因此称之为“不安全的”。然而，我还没有找到演示不安全性示例，所以实际上这可能是有意义的，所以对于勇敢的灵魂，试试吧！

此版本不受安全版本的限制。参数和返回类型可以像任何函数一样具有生命周期。

限制

• 如前所述，安全版本仅在函数没有生命周期类型参数或返回类型时工作。

  • owning_ref crate非常适合解决这个问题。
  • 当然，您可以使用“不安全的”版本。但它可能引起问题。

• 这不是尾调用优化。您仍然可能耗尽堆（尽管这要困难得多）。

• 只支持一个函数。交替递归（f调用g然后g调用f）不受支持。调用相同函数但具有不同泛型参数不受支持。

• 不支持异步函数。

• 不支持结构方法。仅支持独立函数。

• 宏仅理解以文本形式编写的递归调用。

   // This would work:
   recursive(x - 1);
  
   // The macro wouldn't understand this:
   let f = recursive;
   f(x - 1);
  

• 函数参数不能超过12个。

  • 这实际上是pfn crate的限制。

• 不支持在参数位置使用impl Trait。

  • 您可以使用普通、命名泛型。

• 这仍然是非常实验性的。安全版本不包含不安全代码，但即使如此，您仍然应该小心。

• 不支持多线程。

基准测试

基准测试递归线性搜索。请参阅代码。

decurse版本的性能约为正常版本的35%。

对于同时取消注释了linear_search和stack_linear_search的slow(8723)调用的相同基准测试，slow()是一个人工计算，以模仿递归函数实际上执行某些操作的真实用例。

decurse版本的性能约为正常版本的90%。

无论如何，您应该为您自己的用例进行基准测试。这里实现的递归线性搜索甚至不是任何人都会使用的！

我仍然非常想看到您用例的数字。请分享！

鸣谢

这篇由hurryabit撰写的博客文章激发了我创作这个项目的灵感。主要思想基本上是相同的。我的项目更偏向于技巧性，因为我想要避免生成器（需要使用夜间构建版本，并且短期内不会得到稳定），所以我使用了 async/await。