C++ 蹦床

在 C++ 中，trampolining（蹦床技术） 是一种主要用于增强递归函数调用的技术。递归函数是避免问题复杂性并将其转化为多个简单问题的重要工具。然而，过度使用深度递归也有其缺点，例如可能导致调用栈溢出。这时，蹦床技术就派上用场了。

蹦床技术提供了一种将递归转换为迭代的方法，这样就不会有值被推入堆栈，从而避免了堆栈溢出，同时保持了递归逻辑的简单性。蹦床技术的核心思想不是直接递归，而是返回另一个 函数 来表示计算的下一步，可以是函数对象（或等效于函数对象的表示，如 lambda 或函数 指针）。然后，这些 对象 以这种方式进行迭代，由主循环来执行，从而有效地模仿了递归。

当与尾递归调用结合使用时，它通常很有用，因为递归调用是函数中执行的最后一个操作。但并不能保证特定的编译器会使用尾调用优化（TCO）来优化尾递归。蹦床技术通过控制函数调用在堆（heap）而不是在栈（stack）上进行，提供了一种手动实现相同效果的方法。

方法 1：基本函数指针/Lambda 蹦床

如前所述，基本函数指针/Lambda 蹦床是实现 C++ 蹦床技术最简单的方法之一。这种递归形式涉及计算一个过程，该过程直接返回一个函数对象（如 lambda 或函数指针），该对象引用递归函数的下一阶段，而不是进行实际的递归。之后，蹦床机制会一遍又一遍地调用返回的函数对象，直到获得结果，从而消除了深度递归和堆栈溢出的风险。

程序

让我们通过一个例子来说明 C++ 中的蹦床技术。

输出

 
Factorial of 5:
Computing factorial_step(5, 1)
Step 1: Invoking the next recursive step
Computing factorial_step(4, 5)
Step 2: Invoking the next recursive step
Computing factorial_step(3, 20)
Step 3: Invoking the next recursive step
Computing factorial_step(2, 60)
Step 4: Invoking the next recursive step
Computing factorial_step(1, 120)
Step 5: Invoking the next recursive step
Computing factorial_step(0, 120)
Base case reached with result = 120
Final result after 5 steps: 120
Factorial of 5 is 120
Factorial of 7:
Computing factorial_step(7, 1)
Step 1: Invoking the next recursive step
Computing factorial_step(6, 7)
Step 2: Invoking the next recursive step
Computing factorial_step(5, 42)
Step 3: Invoking the next recursive step
Computing factorial_step(4, 210)
Step 4: Invoking the next recursive step
Computing factorial_step(3, 840)
Step 5: Invoking the next recursive step
Computing factorial_step(2, 2520)
Step 6: Invoking the next recursive step
Computing factorial_step(1, 5040)
Step 7: Invoking the next recursive step
Computing factorial_step(0, 5040)
Base case reached with result = 5040
Final result after 7 steps: 5040
Factorial of 7 is 5040
Factorial of 0:
Computing factorial_step(0, 1)
Base case reached with result = 1
Final result after 0 steps: 1
Factorial of 0 is 1
Factorial of -3 (error case):
ERROR!
Error: Factorial is not defined for negative numbers.

说明

提供的代码演示了使用 std::function 和 lambda 等 C++ 特性 的基于蹦床的递归函数。在此示例中，我们将使用三种概念：variant、std::function 和 lambda 函数来迭代计算数字的阶乘。这种方法通过将递归过程分解为离散的步骤来防止过度递归，并且这些步骤是在循环中计算的，而不是以可能导致调用栈反弹的方式进行递归调用。

这种方法可以防止堆栈溢出问题，同时简化了大多数语言内置的递归逻辑的使用。它还包括输入验证，并详细描述了分步计算过程，以提高计算的可靠性和可解释性。

step 结构封装了一个函数（作为 lambda），该函数计算如何进入下一个递归步骤。一个局部 head 包含两个结构，允许函数在递归步骤和最终 yield 之间切换。

• Std::variant<Done, Step>：std::variant 用于表示 Done 类型或 Step 类型，因为使用了递归，一个步骤可以返回 Done（表示递归已完成），而另一个步骤可以返回 Step（表示需要更多递归）。此 variant 用于在循环中模拟递归，而不是使用调用栈，这在循环百分比递归时很重要。
• 阶乘步函数 (factorial_step)：factorial_step 函数是用于计算数字阶乘的普通递归阶乘函数。它不是直接调用此函数。相反，它返回一个 Done 调用（当到达基本情况，即 n == 0 时）或一个 Step 调用（其中包含一个用于下一个递归步骤的 lambda）。每次调用此函数都会返回一个包装了顶层逻辑的 lambda（在 Step 的情况下）或最终的累加器（在 Done 的情况下）。
• 蹦床函数：蹦床函数通过重复应用给定的递归来控制评估过程。它接受来自 factorial_step 的第一个调用。之后，它会检查它是 Done 还是 Step 中还有更多需要处理的步骤。

如果找到一个 Step，它会调用存储在 Step 中的 lambda，以获取下一个 Step 或结果。这意味着递归采用迭代循环而不是调用栈利用来进行递归。它会持续重复，直到调用 Done 值；因此，最后一个值将作为结果返回。

• 错误处理：类型检查确保只有在向 factorial 函数提供正整数值时，var 方法才会起作用。如果负数被传递给 factorial_step 函数，它会抛出 std::Argument: System.InvalidArgument 异常。此异常通过调用 compute_factorial 来返回，compute_factorial 被重定向到打印错误消息。
• 步骤日志记录：此任务主要涉及代码调试范例和计算过程。因此，代码包含多个将每个步骤中计算出的值输出到控制台的操作。此函数演示了递归如何从一个 n 级别移动到另一个级别，最后一个是停止因子。它还记录了在获得结果之前所采取的步骤数，这使得理解控制流序列并因此控制性能变得容易。

复杂度分析

时间复杂度

给定代码的时间复杂度是根据算法计算数字 n 的阶乘所使用的递归调用次数来分析的。

阶乘计算

如“factorial_step”中所述，一种解决递归方法是每一步都减小 n，直到最终达到 0。

关于此代码的一个重要说明是，对于任何给定的数字 n，将要进行的递归步骤数等于 n。之后，我们可以将构造的时间复杂度定义如下：

在步骤 i 的构造中有两个操作，还有一个乘法运算 (n*acc)，它需要恒定的时间，即 O(1)。

因此，递归步骤的数量，也就是乘法的数量是 n。

蹦床函数

蹦床函数 通过调用存储在 Step 结构中的 lambda 函数来遍历所有 n 个递归步骤。

由于在最坏的情况下需要处理 n 个递归步骤，因此也需要 O(n) 的时间，因为它涉及调用 lambda 和更新状态。

因此，我们得出结论，使用这种蹦床方法获取阶乘的时间复杂度为 O(n)，因为蹦床迭代 n 次，并且每次迭代都需要恒定的时间。

空间复杂度

时间复杂度以计算步骤来描述，而空间复杂度是存储计算中使用的变量和数据结构所需的空间量。

递归调用处理

通常，递归函数预计会利用调用栈上的 O(n) 空间，因为每次递归调用都会在栈上创建一个新的帧。

事实上，我们在之前的蹦床操作中遇到的递归通过使用循环被转化为迭代形式。空间复杂度为 O(1)，因为蹦床函数不是递归的，而是执行循环来完成执行。

std::variant 和 Lambda 的内存

为了表示每个递归步骤，定义了一个包含 lambda 函数的 Step 对象。lambda 是按值捕获的，因此对于每个步骤，都会创建一个新的 lambda，它捕获 n 和 acc 的当前值。由于有 n 个步骤，并且在每个步骤都形成一个 lambda 函数，因此存储所有 lambda 的空间复杂度可能为 O(n)。之后，每个 lambda 存储当前步骤的信息，即 n 和 acc 的整数值。因此，每个 lambda 不需要显着的空间。

Variant 存储

在这里，std::variant 在任何给定时间都会保存 Done 或 Step 对象，但不是同时。此内存使用量是恒定的，表示为 O(1)，因为 variant 只需要一个位置来存储这两个结构中的一个。

因此，代码的空间复杂度变为 O(n)，因为代码需要存储 n 个 lambda，每个 lambda 都包含关于递归步骤的信息。但是，由于这些 lambda 是在 堆 上创建的，而不是在调用栈上创建的，因此代码不会出现堆栈溢出。