C++ 中的有限递归和无限递归

递归是计算机科学和编程的核心概念之一，其中一个函数调用自身来解决给定的问题。这种方法在解决可以将问题分解为多个具有相同解决方案的类似问题时非常有效。迭代是关于函数将具有挑战性的问题分解成易于管理的各个组件。

• 在 C++ 中，递归用于多个函数，例如阶乘和斐波那契数列等数学计算，以及图中的复杂算法，如树遍历、排序、搜索等。通常，附加数据也会导致递归比迭代方法产生更简洁优雅的解决方案。
• 然而，那些掌握这种力量的人应该出于正当理由使用它，并利用其影响力来造福社会他人。递归函数的定义非常棘手，必须将其处理到适当的函数终止条件。如果递归函数没有基本情况（即不再进行后续递归调用的条件），则可能导致程序陷入无限递归，从而导致堆栈溢出。发生这种情况是因为对函数的直接调用会消耗一部分堆栈内存，如果程序处于递归控制之下，那么堆栈内存空间总有一天会被耗尽。
• 任何程序员区分有限递归和无限递归至关重要。递归函数是调用自身的程序，其方式是产生无限次调用的解决方案；有限递归在数量上受到限制，因为它被确定在已经定义的特定点或实例处终止函数。
• 上述公式每次都逐渐将递归调用减小到更接近基本情况，从而确保递归链会终止。然而，无限递归没有这样的停止点，主要是由于缺少基本情况或由于逻辑错误，导致函数无法停止，因此程序可能会陷入非终止调用，从而导致程序崩溃。

这篇博客文章的主要目标是让读者了解 C++ 中的有限递归和无限递归。读者将能够很好地理解什么是递归，什么不是递归，并清晰地学习如何在实践中应用递归，以及技巧和实际的最佳实践。无论您是新手还是专业编码员，很少有技术比深入理解递归更有价值。

有限递归

定义

据说有限递归是一种递归，其中递归函数被赋予一个基本情况，即可以或可以定义终止点。这个基本情况有助于结束递归调用的循环，以防止它们永远循环下去，这为函数提供了足够的时间来执行并返回最终结果。

关键组件

• 基本情况： 这是递归结束的基石。这是问题可以通过不深入问题的情况下解决的基本情况。
• 递归情况： 通常被称为函数的基本部分，因为它负责将问题分解成更小的部分并调用递归。当我们完成递归调用时，它应该将函数级别向前推进一个步骤，使其更接近基本情况。

它的工作原理

• 最后，递归是一种递推，其中递归函数的每次调用都会改变调用内的参数，使其能够满足基本情况。
• 例如，在需要求一个数的阶乘的情况下，每次递归调用都处理一个比前一个数少一的数，直到达到一，这也就是基本情况。
• 如果无法满足基本情况，递归控制将继续进行，直到函数返回一个值，并且所有递归调用开始返回，整合它们的值。
• 递归函数是调用自身的函数示例，如果开发人员不小心，这些函数将无限递归并导致堆栈溢出；因此，使用有限递归至关重要。
• 无限递归不适用于递归解决问题，因为它有无限循环的风险。相比之下，有限递归是有效的，因为可以定义结束情况。通过这样做，递归函数的执行只会朝着建立基本情况的方向进行。

无限递归

定义

循环递归发生在递归函数没有结束条件或结束条件被排除时。这会导致递归函数，并使函数调用自身多次，直到堆栈内存空间被用尽，导致堆栈溢出和程序终止。

原因

• 缺少基本情况： 函数没有 if 子句，该子句将在某个阶段结束递归调用。
• 基本情况条件不正确： 基本情况条件存在；然而，由于逻辑问题，基本情况永远不会出现。
• 没有向基本情况进展： 每次递归调用都是如此，函数无法到达基本情况并继续递归。

后果

导致无限的递归会导致对该函数的连续调用而没有停止的机会，从而成为堆栈内存的频繁消耗者。这最终会导致堆栈溢出，因为没有更多的堆栈内存，程序将被中止。

示例场景

让我们以一个本应从某个数字倒数到零的倒计时函数为例。如果函数没有正确地递减数字，该函数将继续通过参数循环，直到达到基本情况，即数字等于零。

避免无限递归

为了避免无限递归

• 对于每个递归函数，请确保有一个明确的基本情况，可以在一步内到达。
• 检查每次递归调用后，问题是否越来越接近基本情况。
• 为了验证递归调用的正确功能，请在递归函数中嵌入调试工具，例如打印语句或调试辅助工具。

有限递归的例子：二分查找

输出

 
Element is present at index 3    

说明

• 第一个操作是一个基本情况，它验证区间是否正确（右 >= 左）。
• 如果它是中间项，换句话说，中点，则提供的函数返回索引。
• 它的结果是，如果目标小于中间元素，则函数转到左侧子数组。
• 如果目标更大，函数则在右侧子数组中搜索它。
• 此过程继续进行，直到找到目标对象或不再获得时间有效性。

无限递归的例子：错误的求和计算

输出

 
... (infinite output until stack overflow)    

说明

• 函数 faultySum 确实是一个递归函数，当传递相同的 n 值时，它会不断调用自身。
• 因此，永远不会进入“?n <= 0?”的基本情况，这意味着该函数具有无限递归和随后的堆栈溢出。

在 C++ 中使用递归的优缺点

递归是编程中最基本的主题之一，其中函数迭代自身来解决问题。尽管如此，该系统也伴随着其缺点。以下是在 C++ 中使用递归的一些优缺点。虽然递归使解决方案优雅简洁，但执行时间比正常迭代长。

递归的优点

• 简单优雅： 通常，递归算法比迭代算法看起来更简单，更容易理解，这是因为某些问题（如树遍历、阶乘计算、斐波那契数列等）固有的递归性质。
• 代码长度缩减： 递归在代码可读性方面有优势，主要是因为它简洁且能够消除对复杂循环和额外数据结构的需求。
• 自然适用于某些问题： 树和图的遍历、分治算法（如快速排序、归并排序）和回溯问题（如解迷宫、谜题等）。
• 状态管理： 这也意味着每次递归调用都会创建一个新的函数作用域，可以方便地处理与状态相关的问题，而不必依赖全局变量和/或复杂的状态管理系统。

递归的缺点

• 性能开销： 当一个函数调用其他函数时，会产生开销，例如用于创建新调用堆栈帧的内存，以及用于其他函数调用的时间。这主要是因为在处理大型输入值时，递归算法可能不如其迭代对应项高效。
• 堆栈溢出： 递归调用中的连续导致堆栈内存使用。如果由于某种原因，递归深度超过预定限制，就会导致堆栈溢出，程序停止工作。深度递归或无限递归是一种特殊的机制，风险相当严重。
• 调试困难： 使用递归函数有时可能难以调试，因为有多个函数调用，并且在尝试确定程序流程和变量如何在多个递归级别上运行，有时会很困难。
• 理解复杂性： 这对于代码来说是一个优势，因为递归可以降低代码的复杂性，但它也是一个缺点，因为对于不习惯递归逻辑的人来说可能很难。新程序员在某些方面可能更容易理解递归解决方案而不是迭代解决方案。

结论

C++ 中的递归是一种有效的程序设计范式，具有简单性的优点，大多数问题或现象最好用递归来描述，例如树遍历、分治算法、回溯技术等。它们提供了更短、更易读的代码，因为消除了复杂的循环和辅助数据结构。这意味着递归可以有效地处理函数式语言应用中状态的问题，而无需使用全局变量，因为函数作用域可以作为问题的补救措施。

此外，测试和调试是执行构建和运行周期迭代时需要进行的批判性组成部分，以避免陷入循环调用或达到计算机内存堆栈的限制。通过上述赞赏和欣赏的观点，程序员在考虑递归时，可以获得关于如何以及何时使用递归以及如何有效创建递归的宝贵信息，从而以更低的复杂性和更高的可靠性达到结果。C++ 中的递归是最重要的知识之一，尽管其使用被认为是良好的实践，但应谨慎对待，并且只有在理解了一些重要规则之后。