`

循环(迭代)与递归的区别

阅读更多

循环(迭代)与递归的区别

 

1。递归算法与迭代算法的设计思路区别在于:函数或算法是否具备收敛性,当且仅当一个算法存在预期的收敛效果时,采用递归算法才是可行的,否则,就不能使用递归算法。

当然,从理论上说,所有的递归函数都可以转换为迭代函数,反之亦然,然而代价通常都是比较高的。但从算法结构来说,递归声明的结构并不总能够转换为迭代结构,原因在于结构的引申本身属于递归的概念,用迭代的方法在设计初期根本无法实现,这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时,通常采用递归的方式而不是采用迭代的方式的原因,一个极典型的例子类似于链表,使用递归定义及其简单,但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩,尤其是在遇到环链、图、网格等问题时,使用迭代方式从描述到实现上都变得很不现实。

 

2。递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解,容易编程。但递归是用栈机制实现的(c++),每深入一层,都要占去一块栈数据区域,对嵌套层数深的一些算法,递归会力不从心,空间上会以内存崩溃而告终,而且递归也带来了大量的函数调用,这也有许多额外的时间开销。所以在深度大时,它的时空性就不好了。

循环其缺点就是不容易理解,编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加,没什么额外开销。空间上没有什么增加。

 

3。局部变量占用的内存是一次性的,也就是O(1)的空间复杂度,而对于递归(不考虑尾递归优化的情况),每次函数调用都要压栈,那么空间复杂度是O(n),和递归次数呈线性关系。

 

4。递归程序改用循环实现的话,一般都是要自己维护一个栈的,以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈,那其实这个递归程序这样写只是意义明显一些,不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态,以便回溯。

原理上讲,所有递归都是可以消除的,代价就是可能自己要维护一个栈。而且我个人认为,很多情况下用递归还是必要的,它往往能把复杂问题分解成更为简单的步骤,而且很能反映问题的本质。

 

 

首先,递归和递推又一定的相似性(当然了,不然怎么会提出这个问题?)

这两个问题都可以描述为以下形式:

f(n)=g(f(n-1)f(0))

这是二者的共同特点。

 

不同点:

1,从程序上看,递归表现为自己调用自己,递推则没有这样的形式。

2,递归是从问题的最终目标出发,逐渐将复杂问题化为简单问题,最终求得问题

是逆向的。递推是从简单问题出发,一步步的向前发展,最终求得问题。是正向的。

3,递归中,问题的n要求是计算之前就知道的,而递推可以在计算中确定,不要求计算前就知道n

4,一般来说,递推的效率高于递归(当然是递推可以计算的情况下)

 

由于一切递归问题都可以转化为循环求解,因此我们可以定义广义递归:

 

如果转化为循环后,需要自己维护堆栈,则仍称为是递归的。

 

在这个定义下,有些问题适用于用递归求解,如梵塔问题有些问题适用于用递推来做,如求满足N!>M条件时最小的N。有些问题二者都可以,如给定N时的阶乘问题。至于可读性,与问题有关,不能一概而论。

 

递归其实就是利用系统堆栈,实现函数自身调用,或者是相互调用的过程。在通往边界的过程中,都会把单步地址保存下来,知道等出边界,再按照先进后出的进行运算,这正如我们装木桶一样,每一次都只能把东西方在最上面,而取得时候,先放进取的反而最后取出。递归的数据传送也类似。但是递归不能无限的进行下去,必须在一定条件下停止自身调用,因此它的边界值应是明确的。就向我们装木桶一样,我们不能总是无限制的往里装,必须在一定的时候把东取出来。比较简单的递归过程是阶乘函数,你可以去看一下。但是递归的运算方法,往往决定了它的效率很低,因为数据要不断的进栈出栈。这时递推便表现出它的作用了,所谓递推,就是免除了数据进出栈的过程。也就是说,不需要函数不断的向边界值靠拢,而直接从边界出发,直到求出函数值。比如,阶乘函数中,递归的数据流动过程如下:

 

f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}

 

而递推如下:

 

f(0)-->f(1)-->f(2)-->f(3)

 

由此可见,递推的效率要高一些,在可能的情况下应尽量使用递推。但是递归作为比较基础的算法,它的作用不能忽视。所以,在把握这两种算法的时候应该特别注意。

 

分享到:
评论

相关推荐

    迭代与递归的区别

    在计算机编程中,迭代与递归是两种常用的解决重复性问题的方法。它们各自有不同的特点和适用场景。理解它们之间的区别,对于编写高效和优雅的代码至关重要。 迭代是一种方法,它通过重复执行一组指令来逐步逼近最终...

    迭代与递归算法

    例如,"递归和迭代的区别.doc"可能阐述了递归如何通过递归公式解决斐波那契序列或其他分治策略问题,如分治法的基本思想文档所讨论的那样。递归在解决某些问题时有其独特的优势,因为它能够简化代码结构,但需要注意...

    DSAinC++3-遍历迭代与递归1

    第3章 遍历、迭代与递归 在计算机科学中,遍历、迭代和递归是三种常见的解决问题的方法,特别是在数据处理和算法设计中。遍历是访问集合所有元素的过程,通常按照一定的顺序,确保每个元素仅被访问一次。这种操作在...

    「循环」「遍历」「迭代」「递归」的区别?

    迭代与循环看似相似,却有不同之处。 循环:循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。 遍历 遍历(traversal),指的是按照一定的规则访问树形结构中的每个节点,...

    C语言实现 求二项式各项系数(迭代,递归)

    本文将围绕“C语言实现求二项式各项系数(迭代,递归法)”这一主题,深入探讨如何利用C语言通过迭代和递归两种方法来计算二项式系数,这不仅体现了C语言的强大功能,也展示了编程中不同算法的运用与对比。...

    递归与迭代算法及其在JAVA语言中的应用.pdf

    递归与迭代是算法设计中两种常见的解决问题的方法,它们在Java语言中的应用广泛且具有深远的意义。递归算法通过方法内部调用自身来解决问题,它适合于可以分解为相似子问题的问题;而迭代算法则通过循环结构,不断...

    C++:斐波那契数列(迭代和递归)

    总结来说,C++提供了多种方式来实现斐波那契数列,包括迭代和递归,以及递归的优化形式——记忆化。在实际应用中,我们需要根据问题规模和性能需求选择合适的方法。对于小规模的计算,递归可能更为直观;而大型计算...

    c语言-阶乘算法(迭代和递归).docx

    C语言-阶乘算法(迭代和递归) C语言-阶乘算法是计算阶乘的经典算法,包括迭代算法和递归算法两种实现方式。阶乘是数学中的一种运算符号,表示一个数字的所有正整数因子的乘积,如n! = n * (n-1) * (n-2) * (n-3) * ....

    循环和递归在算法中的应用

    循环和递归是编程中两种重要的控制结构,它们在算法设计中扮演着核心角色。循环是基础,递归则是其特殊形式,具有更强的抽象能力。递归在冯·诺依曼计算机体系中虽不被视为基本控制结构,但可以通过精心设计的循环...

    PHP迭代与递归实现无限级分类

    本文将探讨两种实现无限级分类的方法:循环迭代和递归。 1. 循环迭代实现 这种方法是通过遍历数据数组,根据每个元素的“father”属性来构建父子关系。关键在于利用数组引用,将子元素添加到其父元素的“son”属性...

    递归与迭代的区别1

    递归与迭代是两种常见的编程方法,用于解决各种复杂问题,特别是在算法设计中。它们各自具有独特的特性和适用场景。 **递归** 是一种程序调用自身的技术,它通过将大问题分解为与原问题相似但规模更小的子问题来...

    第12讲 递归和迭代.pptx

    枚举算法,递归与分治策略,递归与迭代的思想、求最大值最小值、线性查找、二分查找与冒泡排序以及选择与交换排序、插入和希尔排序。本课程除了强调经典的算法理论和模型,亦兼顾编程实践能力。力图使得学员面对复杂...

    Java程序设计中递归与迭代的比较.pdf

    递归是函数或方法直接或间接调用自身,将复杂问题分解为相似的子问题来解决,而迭代则使用循环结构逐步推进问题的解决。 1. 递归: - **递归公式**:递归的核心是定义一个递归关系,例如在计算阶乘的例子中,n! = ...

    python中的函数递归和迭代原理解析

    在Python编程中,函数递归和迭代是两种不同的解决问题的方法,它们各自具有独特的特性和应用场景。本文将深入解析这两种概念,帮助你更好地理解和运用它们。 首先,让我们详细探讨函数递归。递归是一种程序设计技术...

    递归和迭代1

    与递归不同,迭代不涉及自我调用,而是使用循环结构(如 for 循环、while 循环)来重复执行某段代码。 #### 2.2 迭代的基本要素 - **初始条件**:定义迭代的起始状态。 - **迭代步骤**:每次循环时更新的状态。 - ...

    Java中的迭代和递归详解

    与递归不同,迭代不会直接调用自身,而是通过更新变量或状态来推进计算。 例如,计算阶乘的迭代实现: ```java int factorial(int n) { int product = 1; for (int i = 2; i ; i++) { // 循环 product *= i; } ...

    递归与迭代算法及其在JAVA语言中的应用.zip

    在编程世界中,递归和迭代是两种基本的解决问题的方法,尤其在Java语言中,它们在...在阅读“递归与迭代算法及其在JAVA语言中的应用.pdf”这份资料后,相信你将对这两者有更深入的理解,并能灵活地应用到实际项目中。

    Java之递归和迭代用法

    比较递归与迭代: 1. **空间效率**:递归可能导致大量的函数调用,占用更多的内存(堆栈空间),而迭代则通常对内存需求较低。 2. **时间效率**:在某些情况下,迭代可能更快,因为递归可能会导致额外的函数调用...

    循环递归算法设计.pdf.ppt

    在本章中,我们将深入探讨循环与递归的设计要点,以及如何利用它们优化算法效率。 首先,让我们关注循环设计。循环是程序设计的基础,通过循环可以实现重复执行某段代码的操作。在设计循环时,有两个关键点需要注意...

    递归与迭代程序设计.ppt

    在编程领域,递归与迭代是两种常见的解决问题的方法,它们各有特点,且在特定场景下有各自的优缺点。本篇文章将深入探讨这两种方法,并通过具体的示例解释如何将递归算法转换为迭代算法。 首先,让我们理解递归算法...

Global site tag (gtag.js) - Google Analytics