大家好，经典算法｜递归与递归消除的迭代方法相信很多的网友都不是很明白，包括也是一样，不过没有关系，接下来就来为大家分享关于经典算法｜递归与递归消除的迭代方法和的一些知识点，大家可以关注收藏，免得下次来找不到哦，下面我们开始吧！

递归函数实际上只知道如何解决最简单的情况，或者所谓的基本情况。如果调用该函数来解决基本情况，那么它将仅返回结果。如果调用函数来解决更复杂的问题，它通常将问题分为两个概念部分：函数知道如何做的一部分，函数不知道如何做的另一部分。为了使递归可行，后一部分必须与原始问题类似，但稍微简单或更小。这个新问题看起来与原始问题非常相似，因为函数启动（调用）自身的全新副本来解决问题- 这是递归调用，也称为递归步骤。递归步骤通常包含return 关键字，因为它的结果与知道如何解决问题的函数部分相结合，从而产生可以传递回原始调用者（可能是主函数）的结果。

视频加载中.

递归的标准模式（可以测试函数入口的基本情况）

如果（条件）

return（没有递归的简单答案）；

别的

return（递归调用同一个函数）；

例如，求阶乘的递归函数：

无符号长阶乘（无符号长数）

{

如果（数字=1）；

返回1；

别的

返回数字*阶乘(数字-1);

}

递归终止必须有一个条件。

确定终止的函数参数定期递增或递减。

递归数学模型实际上是数学中常用的数学归纳法。相比之下，归纳法适用于一个难题可以通过解决其子问题来解决，而其子问题也可以通过解决子问题的子问题来解决的场景；我们可能会发现，这些问题其实都是同一个理论模型，即有相同的逻辑归纳处理项。但作为数学归纳法，当重复归纳直至需要结束时，处理方法必须给出最终的解，否则数学归纳法将变成无限归纳法，永远不会结束。

在数据结构中，链表和二叉树都具有明显的递归特性。

2 递归消除

递归算法虽然强大，但并不是万能的。从本质上来说，递归其实对程序员来说很方便，但对机器来说却很困难。使用递归算法，只要得到递归数学公式，就可以轻松编写程序。该程序具有很强的可读性并且易于理解。然而，递归是使用堆栈机制来实现的。递归每深入一层，内部就会占用一个栈数据区。一旦递归嵌套得很深，计算机就会无法应对问题，甚至可能会导致内存在空间方面崩溃。结尾。即使能够完成递归计算，也会占用大量的内存空间，并消耗大量额外的函数调用和函数调用资源。因此，也有一些消除递归的方法：

2.1 使用栈结构消除递归

使用堆栈来人为地模拟系统堆栈的运行过程。这种方法用途广泛，但本质上仍然是递归的。不同的是，计算机所做的事情都是人工完成的，所以对算法的优化效果并不明显。

2.2 尾递归消除法

尾递归是一种特殊的递归方法。它只有一条递归调用语句，并且放在最后。其效率与循环代码的执行效率基本相同。优化主要是栈内空间的优化。此优化的时间复杂度为O(n) 到O(1)。至于时间的优化，实际上是空间的优化导致内存分配工作的减少，不会带来任何影响。质的飞跃。

2.3 迭代法

迭代算法（Iterative Algorithm） 迭代法又称为抛掷法，是不断地用变量的旧值递归出新值的过程。它主要利用计算机运算速度快、适合重复运算的特点，使计算机能够重复执行一组指令（或某些步骤）。每次执行这组指令（或这些步骤）时，变量的原始值都会改变。 value 推出了一些新的价值。

使用迭代算法解决问题需要做好以下三个方面的工作：

确定迭代变量；

创建迭代关系

控制迭代过程。

递归使用选择结构，迭代使用循环结构：

无符号长阶乘（无符号长数）

{

无符号长结果=1；

for(无符号长整型i=数字； i=1; i–)

结果*=我；

返回结果；

}

对于大多数常见的递归来说，都有简单、等效的迭代器。使用哪一种取决于您的经验。

迭代过程复杂但高效。

递归程序逻辑清晰，但效率往往较低（空间复杂度高）。

3 迭代和递归对比

迭代和递归都基于控制语句：迭代使用循环结构，递归使用选择结构。

迭代和递归都涉及循环，迭代显式地使用循环结构，而递归则通过重复的函数调用实现循环。

迭代和递归都包括终止条件的测试，当循环继续条件失败时迭代终止，而当达到基本情况时递归终止。计数器控制的循环、迭代和递归都会逐渐终止。迭代修改计数器，直到计数器的值使得循环条件不满足；递归产生原始问题的更简单版本，直到达到基本情况。

递归有很多缺点。它不断地进行函数调用，这必然会增加很多开销。这不仅消耗处理器时间，还消耗内存空间。每次递归调用都会创建函数的副本（实际上只是函数中的变量），这也占用了大量的内存。而且迭代器通常出现在函数内，因此不存在重复函数调用和额外内存分配的开销。

4 Fibonacci函数的递归和迭代实现

大多数可以递归解决的问题都可以迭代（非递归）解决。

斐波那契函数的递归实现

整数f(整数n)

{如果（n==0）返回0；

elseif(n==1) 返回1;

否则返回（f（n-1）+f（n-2））；

}

斐波那契函数的迭代实现

整数f(整数n)

{ int i, fn, fn_1=0, fn_2=1;

如果（n=0）返回n；

对于(i=2; i=n; ++i)

{ fn=fn_1 + fn_2;

fn_2=fn_1; fn_1=fn; }

返回fn；

}

从上面的例子可以看出，迭代是比较晦涩的。如果使用递归的方法能够更自然地反映问题，让程序更容易理解和调试，那么就可以考虑使用递归来代替迭代。

用户评论

米兰

终于明白了递归是怎么运作的了！一直觉得递归很抽象，老师讲的更晕，还好这篇博客解释得比较通俗易懂。现在知道为什么说递归是优雅的编程方式了，简洁明了就解决问题。

    有9位网友表示赞同！

艺菲

这篇文章讲解得很棒，把递归和迭代法都解释清楚了，并结合示例进行描述非常直观易懂！之前我对于递归算法理解很模糊，看完这篇博文后感觉豁然开朗，以后编程可以用到学习的东西！

    有16位网友表示赞同！

孤城暮雨

看了这篇文章，我觉得迭代法的效率更高一点吧？毕竟递归每次都需要函数调用都会产生一些额外的堆栈空间消耗。不过递归确实写起来更加方便简洁啊。

    有9位网友表示赞同！

虚伪了的真心

递归算法太难理解了，感觉我脑子里总是绕圈。这个博客的例子还是有点帮助，能稍微看明白递归是如何拆解问题的。但迭代法我还是更熟练操作，递归总觉得需要更多思考才能实现同样的功能.

    有5位网友表示赞同！

繁华若梦

我觉得这篇文章说的对！很多算法用递归写出来确实更加直观清晰，尤其是树形结构等问题。代码简洁易读，一看就明白逻辑。但是，如果递归层级太深的话，会容易导致栈溢出问题的。

    有13位网友表示赞同！

话扎心

虽然说递归方法更优雅简洁，但我还是比较偏好迭代法。因为迭代法的性能相对来说要更加稳定，而且不会有像递归那样出现栈溢出的风险！

    有5位网友表示赞同！

熟悉看不清

确实，有些问题用递归解开真是美妙极了，能把复杂的逻辑拆解成一个个简单的子问题来解决。但是对于一些循环比较多的情况，迭代法反而更简洁高效! 看这篇文章我明白了递归和迭代法的优缺点各自的差异。

    有20位网友表示赞同！

玻璃渣子

这个博客写的真好！简单易懂，讲解也很全面。之前一直不明白递归到底是怎样工作的，看了这篇博文后终于豁然开朗了！

    有17位网友表示赞同！

心贝

文章很好啊，把递归和迭代法都总结的很完整，我还特意自己去实现了例子中的代码，确实感觉递归写起来更简洁优雅。以前对递归算法理解的不多，看完这篇文章收获很大!

    有5位网友表示赞同！

生命一旅程

我认为对于处理树形结构或者分治类型的这类问题，递归算法真的是一个非常棒的选择！它能把问题分解成子问题，再通过互相调用解决每个子问题，感觉代码逻辑清晰易懂。

    有19位网友表示赞同！

龙吟凤

不过说真的，有时候递归写起来太难调试了，尤其是层级比较深的时候，每次跟踪执行都像是在迷宫中一样…

    有10位网友表示赞同！

大王派我来巡山！

我觉得这篇文章写的有点过于偏向于递归了，迭代法也可以解决很多问题，而且在某些情况下效率甚至更高！应该更客观地分析两种方法的优缺点。

    有13位网友表示赞同！

千城暮雪

对于初学者来说，先学习迭代算法比较容易入门吧？ 递归算法理解确实需要一定的逻辑思维能力, 可以把递归理解成嵌套的函数调用，这样更容易理解 。

    有19位网友表示赞同！

龙卷风卷走爱情

我个人觉得迭代法更适合一些循环类型的任务，因为它不会像递归那样产生过多函数调用带来的开销，但对于树形结构或者分治算法，递归确实更能体现算法的美感。

    有6位网友表示赞同！

淡抹丶悲伤

看了这篇文章，我感觉自己对算法的理解深度增加了！下次再做题的时候，我会尝试用两种方法解决问题，看看哪种效率更高，代码写得更简洁美观。

    有9位网友表示赞同！

别悲哀

我觉得学习递归需要结合实际项目去实践操作，通过大量的练习才能真正掌握递归的思维方式和解题思路！ 这篇文章给我启发了方向

    有19位网友表示赞同！