数据结构中的递归：它是如何工作的、类型以及何时使用

让我们从数据结构中递归的定义开始。 稍后我们将讨论不同类型的递归以及如何使用递归来解决不同的问题。

什么是递归？

简而言之，递归是一种解决问题的方法，在某些情况下，它是一种具有非常特殊和专有属性的编程技术。 在递归中，函数或方法具有调用自身来解决问题的能力。 递归过程涉及通过将问题转化为自身的较小变体来解决问题。

函数调用自身的过程可以直接发生，也可以间接发生。 这种调用的不同导致了不同类型的递归，我们稍后会讨论。 可以使用递归解决的一些问题包括图的 DFS、河内塔、不同类型的树遍历等。 要了解递归和其他数据科学概念，请查看 IIIT-B 的数据科学在线课程。

阅读： 13 个有趣的数据结构项目理念

递归是如何工作的？

递归的概念建立在这样一种思想上，即如果问题以一个或更小的版本表示，则可以很容易地在更短的时间内解决问题。 添加基本​​条件以停止递归是使用此算法解决问题的另一个重要部分。

人们通常认为不可能根据自身来定义实体。 递归证明该理论是错误的。 如果这项技术以正确的方式进行，它可能会产生非常强大的结果。 让我们通过几个例子来看看递归是如何工作的。 什么是句子？ 它可以定义为在连词的帮助下将两个或多个句子连接在一起。 类似地，文件夹可以是用于存储文件和文件夹的存储设备。 祖先可以是家谱中一个家庭成员的父母和另一个家庭成员的祖先。

递归有助于使用一些非常简单的词来定义复杂的情况。 您通常如何定义祖先？ 父母、祖父母或曾祖父母。 这可以继续下去。 同样，定义文件夹可能是一项艰巨的任务。 它可以是任何包含一些文件和文件夹的东西，这些文件和文件夹本身可能是文件和文件夹，并且可以再次继续。 这就是为什么递归使定义情况比平常容易得多的原因。

递归也是一种足够好的编程技术。 递归子程序被定义为直接或间接调用自身的子程序。 调用子程序直接表示子程序的定义已经有了调用已定义子程序的调用语句。

另一方面，子程序的间接调用发生在一个子程序调用另一个子程序时，而另一个子程序又调用了原来的子程序。 递归可以用几行代码来描述一个非常复杂的任务。 现在让我们将注意力转向我们已经触及的不同类型的递归。

另请阅读：要学习的前 6 种编程语言

递归的类型

正如已经提到的，只有两种类型的递归。 让我们看看它们之间有何不同。 直接递归是更简单的方法，因为它只涉及调用原始函数或方法或子例程的单个步骤。 另一方面，间接递归涉及几个步骤。

第一次调用由原始方法对第二个方法进行，后者又调用原始方法。 这个调用链可以包含许多方法或函数。 简单来说，我们可以说间接递归的深度总是存在变化的，而这种深度的变化取决于过程中涉及的方法的数量。

直接递归可用于单独调用单个函数。 另一方面，间接递归可用于在其他函数的帮助下调用多个方法或函数，并且多次调用。 间接递归不会产生开销，而其直接对应物会产生开销。

什么时候使用递归？

在某些情况下，您可以使用递归或迭代。 但是，您应该始终选择看起来更适合问题的解决方案。 当涉及到数据抽象时，递归总是一个合适的选择。 人们经常使用递归定义来定义数据和相关操作。

可以说递归主要是解决与对数据执行不同操作相关的问题的自然解决方案也不会错。 但是，与递归相关的某些事情可能不会使其成为每个问题的最佳解决方案。 在这些情况下，像迭代方法这样的替代方法是最合适的。

递归的实现使用了大量的堆栈空间，这通常会导致冗余。 每次使用递归时，我们都会调用一个方法，从而创建该方法的新实例。 这个新实例携带不同的参数和变量，它们存储在堆栈中，并在返回时获取。 因此，虽然递归是比其他解决方案更简单的解决方案，但它通常不是最实用的。

此外，我们没有一组预定义的规则可以帮助为不同的问题选择迭代或递归。 使用递归的最大好处是它是一种简洁的方法。 这使得阅读和维护它比平时更容易。 但是递归方法并不是我们可用的最有效的方法，因为它们占用大量存储空间并在实现过程中消耗大量时间。

记住一些事情可以帮助您决定为问题选择递归是否是正确的方法。 如果您要解决的问题以递归方式提及并且递归解决方案似乎不那么复杂，您应该选择递归。

您应该知道，在大多数情况下，递归简化了您要使用的算法的实现。 现在，如果与使用迭代和递归相关的复杂性对于给定的问题是相同的，那么您应该使用迭代，因为它更有效的机会更高。

另请查看： 23 门最佳计算机编程课程，以找到工作

结论

但是，在某些情况下，做出决定可能并不那么容易。 您必须在效率和简单性之间做出选择。 如果您是一位经验丰富的设计师，您将确切地知道何时更重视效率，何时选择简单或简洁而不是它是要走的路。

如果您想了解数据结构、数据科学，请查看 IIIT-B 和 upGrad 的数据科学执行 PG 计划，该计划专为在职专业人士创建，提供 10 多个案例研究和项目、实用的实践研讨会、行业指导专家，与行业导师一对一，400 多个小时的学习和顶级公司的工作协助。