算法逻辑理论到循环、递归、递推、迭代、遍历等代码(24500字)(附PDF发“算法逻辑循环”下载)
数据简化DataSimp导读：在语言文字运用、自然语言处理、知识工程和算法设计中，逻辑表达式(logic expression)、程序逻辑(programm logic)、算法逻辑(algorithm logic)、循环结构(loop structure)等非常典型。本文5章25节从其概念和理论逐一细化，直到典型的重复执行类型算法——循环(loop)、递归(recursive)、递推(recurrence)、迭代(iterate)、遍历(traversal)等相应的跨平台语言Java和统一化逻辑编程语言Prolog程序代码示例。
算法逻辑理论到循环、递归、递推、迭代、遍历等代码(24500字)
目录
A 算法逻辑理论到循环、递归、递推、迭代、遍历等代码(23445字)
1. 真值逻辑量的逻辑表达式
2. 描述程序行为的程序逻辑
3. 算法逻辑的三种基本结构
4. 典型算法逻辑之循环简介
5. 循环等重复类型算法程序
参考文献(2742字) Appx(1236字).数据简化DataSimp社区简介
A算法逻辑理论到循环、递归、递推、迭代、遍历等代码(23445字)
算法逻辑理论到循环(loop)、递归(recursive)、递推(recurrence)、迭代(iterate)、遍历(traversal)等代码
文|秦陇纪，数据简化DataSimp©20190126Sat-0227Wed
对自然事物的感受、认知过程中，语文描述、科学理论、工程技术逐步递进，实现从模糊概念到具体知识或产品的落地，整体上思维和认知具有一定复杂性，若只会语言文字之空想作文，则不能完成任何一个具体知识或产品。从语文描述现实世界，到理论描述自然规律，其必然之路是科学实证思维——几何、代数、近世代数、逻辑代数、描述逻辑、数理逻辑、现代逻辑等数学理论和方法。科学实验、科学假说，均需实验支撑，工程技术能力是基本素质。理论和技术丰富并完善了科学之躯，切不可止步于语文表象思维，识字空想而不做实验，无法认知自然本质。
1928年，希尔伯特提出数学23问的28年后，抽象出数理逻辑三大问题，构成他一生思考的终极之问——数学1)完备吗？2)一致吗？3)可判定吗？这三问之含义直指所有数学命题1)是否都可以用一组有限的公理证明或证否？2)可以证明的都相容？3)都有明确程序可在有限时间内判定是真是假？也就是说，作为科学理论工具，数学自身是否完备一致。
希尔伯特纲领性的23问尤其是后三问试图建立作为一切数学的元数学，后来哥德尔证明那是不可能的。数学并不能连续一致地描述数学各分支，更不能描述全部自然规律。但希尔伯特纲领却带来了一系列副产品：图灵机、自动机、广义程序语言……等，理论计算机、计算机工程却发展起来了。为了解CS理论，科学Sciences上期文章简述了科学理论之数学理论主要节点；本期数据简化DataSimp介绍逻辑表达式、程序逻辑和算法逻辑的概念，以及典型的算法逻辑过程之循环算法：递归、递推、遍历、迭代等相关概念和编程代码。
1. 真值逻辑量的逻辑表达式
布尔用数学方法研究逻辑问题，成功建立逻辑演算(又叫逻辑运算、布尔运算)。他用等式表示判断，把推理看作等式的变换。这种变换的有效性不依赖人们对符号的解释，只依赖于符号的组合规律。人们常称这一逻辑理论为布尔代数。20世纪30年代，逻辑代数在电路系统上获得应用，随后，由于电子技术与计算机的发展，出现各种复杂大系统，它们的变换规律也遵守布尔所揭示的规律。
图1：逻辑表达式图
中文名：逻辑表达式，外文名：logic expression，学科：数理科学，类型：数学术语，应用时间：20世纪30年代，逻辑运算：又称布尔运算。[1]
1.1 逻辑运算符
用逻辑运算符将关系表达式或逻辑量连接起来的有意义的式子称为逻辑表达式。逻辑表达式的值是一个逻辑值，即“true”或“false”。C语言编译系统在给出逻辑运算结果时，以数字1表示“真”，以数字0表示“假”，但在判断一个量是否为“真”时，以0表示“假”，以非0表示“真”。
可以将逻辑表达式的运算结果(0或1)赋给整型变量或字符型变量。
C语言中，等于是“==”，不等于是“！=”。
Pascal语言中，等于是“=”，不等于是“<>"
1.2 浮点数运算
浮点数在计算机中不能非常准确地表示，判断两个浮点数是否相同时，通常不使用关系运算符“等于”(==)，而是利用区间判断方法来实现。为了判断x是否等于5.003，可利用如下逻辑表达式：
x>5.002 &&x<5.004
当此逻辑表达式为“真”时，就可以认为x等于5.003
逻辑及性质保真性:所有变量的真值皆为“真”的命题在逻辑或运算后的结果为真。保假性:所有变量的真值皆为“假”的命题在逻辑或运算后的结果为假。[2]
1.3 逻辑表达式改进
通常的数字逻辑电路的设计、教学中，用布尔代数法进行逻辑表达式的运算及简化时，人们一般需要掌握布尔代数的基本定律、结合律、交换律、分配律、互补律、0一1律、吸收律、还原律、狄摩根定理、分解定理等；以及一些规则，例如代入规则、反演规则、对偶规则及一些常用的恒等式等；简化时还可能要用到并项法、吸收法、消去法及配项法、卡诺图等等技巧。
能否得到最优或最简的逻辑表达式，全凭经验及逻辑运算的熟练程度。特别是在进行与或表达式和与异表达式之间的转换与简化时，通常无一般规律可循，较不易把握。利用卡诺图虽然对于变量较少晰U如不多于4个变量的情况)的与一或、或与表达的简化较有效，但对于较多变量以及与或表达式和与异表达式之间的转换与简化，似乎也有点不知所措。[3]
在设计实践和教学中，如果使用推广的吸收律、广义还原律和分解定理等有关的公式，将能更简便地简化逻辑表达式，往往使得似乎无从下手的逻辑简化问题能找到一种有效的出路。[4]
广义吸收律：
x1 f(x1,x2, x3, …xn) = x1 f(1, x2,x3, …xn);
x¯1 f(x1,x2, x3, …xn) = x¯1 f(1,x2, x3, …xn);
1.4 逻辑门数字电路
数字电路中“门”是只能实现基本逻辑关系的电路。最基本的逻辑关系是与、或、非，最基本的逻辑门是与门、或门和非门。逻辑门可以用电阻、电容、二极管、三极管等分立原件构成，成为分立元件门。也可以将门电路所有器件及连接导线制作在同一块半导体基片上，构成集成逻辑门电路。
图2：基本逻辑运算符
(1)与门
与门(AND gate)又称“与电路”、逻辑“积”、逻辑“与”电路。是执行“与”运算的基本逻辑门电路。有多个输入端，一个输出端。当所有的输入同时为高电平(逻辑1)时，输出才为高电平，否则输出为低电平(逻辑0)。
逻辑表达式:F=AB.
(2)或门
或门(OR gate)，又称或电路、逻辑和电路。如果几个条件中，只要有一个条件得到满足，某事件就会发生，这种关系叫做“或”逻辑关系。具有“或”逻辑关系的电路叫做或门。或门有多个输入端，一个输出端，只要输入中有一个为高电平时(逻辑“1”)，输出就为高电平(逻辑“1”)；只有当所有的输入全为低电平(逻辑“0”)时，输出才为低电平(逻辑“0”)。
逻辑表达式: F=A+B.
(3)非门
非门(NOT gate)又称非电路、反相器、倒相器、逻辑否定电路，简称非门，是逻辑电路的基本单元。非门有一个输入和一个输出端。当其输入端为高电平(逻辑1)时输出端为低电平(逻辑0)，当其输入端为低电平时输出端为高电平。也就是说，输入端和输出端的电平状态总是反相的。非门的逻辑功能相当于逻辑代数中的非,电路功能相当于反相,这种运算亦称非运算。
逻辑表达式: F=A¯
(4)与非门
与非门(NAND gate)是数字电路的一种基本逻辑电路。若当输入均为高电平(1)，则输出为低电平(0)；若输入中至少有一个为低电平(0)，则输出为高电平(1)。与非门可以看作是与门和非门的叠加。
逻辑表达式: F=(AB)¯¯
图3：与非门逻辑状态表
(5)或非门
或非门(NOR gate)是数字逻辑电路中的基本元件，实现逻辑或非功能。有多个输入端，1个输出端，多输入或非门可由2输入或非门和反相器构成。只有当两个输入A和B为低电平(逻辑0)时输出为高电平(逻辑1)。也可以理解为任意输入为高电平(逻辑1)，输出为低电平(逻辑0)。
逻辑表达式: F=(A＋B)¯¯
(6)异或门
异或(exclusive OR)数学符号为⊕(圆圈内为加号)，计算机符号为xor。异或门(Exclusive-OR gate，简称XOR gate，又称EOR gate、ExOR gate)是数字逻辑中实现逻辑异或的逻辑门。有多个输入端、1个输出端，多输入异或门可由2输入异或门构成。若两个输入的电平相异，则输出为高电平1；若两个输入的电平相同，则输出为低电平0。亦即，如果两个输入不同，则异或门输出高电平。
逻辑表达式: F=A⊕B
(7)同或门
同或XNOR(Exclusive NOR)数学符号为⊙(圆圈内为点)，计算机符号为xnor。同或门(XNOR gate或equivalence gate)也称为异或非门，是数字逻辑电路的基本单元，有2个输入端、1个输出端。当2个输入端中有且只有一个是低电平(逻辑0)时，输出为低电平。亦即当输入电平相同时，输出为高电平(逻辑1)。[5]
逻辑表达式: F=A⊙B
(注1：资料来自百度百科等[1-6]。词条标签：数理科学，科学学科。本词条认证专家为肖志勇江南大学副教授审核。[6]词条统计：浏览94525次，编辑次数：18次历史版本，2018-06-06最近更新：w_ou。)
2. 描述程序行为的程序逻辑
程序逻辑(programm logic)是描述和论证程序行为的逻辑，又称霍尔逻辑。霍尔逻辑(HoareLogic)又称弗洛伊德-霍尔逻辑(Floyd–Hoarelogic)，是英国计算机科学家东尼·霍尔(C.A.R.Hoare)开发的形式系统，随后为Hoare和其他研究者所精制。这个系统的用途是为了使用严格的数理逻辑推理来替计算机程序的正确性提供一组逻辑规则。
中文名：程序逻辑，定义：描述和论证程序行为的逻辑，别称：霍尔逻辑，学科：计算机，开放分类：计算机术语、计算机科学技术名词，两者关系：程序和逻辑有着本质的联系。
2.1 程序逻辑简介
程序逻辑的基本方法是先给出建立程序和逻辑间联系的形式化方法，然后建立程序逻辑系统，并在此系统中研究程序的各种性质。如果把程序看成一个执行过程，它接收一些信息，又输出一些信息。用逻辑公式描述对输入和输出信息的要求，就可以建立逻辑公式和程序间的联系，表示为{P}S{Q}。此公式表示：如果程序S执行前程序变量的值满足前置条件P，且程序S终止，则程序S执行终止后，程序变量的值满足后置条件Q。其中P和Q为有关程序变元的逻辑表达式；P称为S的前置条件；Q称为S的后置条件。如果进一步建立一套关于这类公式的推理规则，就能得到一个描述程序行为的逻辑系统，可以在此系统中研究程序的性质，这就是程序逻辑。
程序是在机器中执行的，程序中每个语句的执行导致机器状态的变化，因此程序的执行又可以由机器状态变化的序列表达。数理逻辑中的模态逻辑正是描述动态变元变化的一种逻辑，因此以模态逻辑为基础也可揭示逻辑与程序间的深刻联系。
2.2 霍尔逻辑起源
60年代中期，美国R.W.弗洛依德把框图程序对应为逻辑公式，提出使用逻辑描述和分析程序的想法。1969年前后，英国C.A.R.霍尔首次给出一类程序语言的逻辑系统，提出程序部分正确性的形式验证规则(见程序验证)，首次发表在论文"计算机程序的公理基础"中，随后为其他研究者所精制。这个系统的用途是为了使用严格的数理逻辑推理计算机程序的正确性提供一组逻辑规则。
这个想法起源于罗伯特·弗洛伊德较早的研究，Hoare认可Robert Floyd的早期贡献，他为流程图提供了类似的系统。[7]70年代初，波兰和瑞士一些学者提出使用算法逻辑描述和分析程序，这是第一次把模态逻辑引入程序逻辑的尝试。70年代中期，有些科学家进一步提出使用动态逻辑和时态逻辑，描述和论证程序，推动了程序逻辑的研究。
2.3 霍尔三元组公式
霍尔逻辑的中心特征是霍尔三元组(Hoaretriple)。这种三元组描述一段代码的执行，如何改变计算的状态。Hoare三元组有如下形式
{P}C{Q}
这里的P和Q是断言而C是命令。P叫做前条件而Q叫做后条件。断言是谓词逻辑的公式。这个三元组在直觉上读做：只要P在C执行前的状态下成立，则在执行之后Q也成立。注意如果C不终止，也就没有"之后"了，所以Q在根本上可以是任何语句。实际上，你可以选择Q为假来表达C不终止。事实上，这种情形叫做"部分正确(partial correctness)"。如果C终止并且在终止时Q是真，则表达式被称作 "全部正确性(total correctness)"。终止必须被单独证明。+
霍尔逻辑为简单的命令式编程语言的所有构造提供了公理和推理规则。除了给Hoare论文中的简单语言的规则，其他语言构造的规则也已经被Hoare和很多其他研究者开发完成。包括并发、过程、goto语句和指针。[8] 命令式编程(imperative programming)，是一种描述计算机所需作出的行为的编程典范。几乎所有计算机的硬件工作都是命令式的；几乎所有计算机的硬件都是设计来运行机器代码，使用命令式的风格来写的。较高端的命令式编程语言使用变量和更复杂的语句，但仍依从相同的典范。菜谱和行动清单，虽非计算机程序，但与命令式编程有相似的风格：每步都是指令，有形的世界控制情况。因为命令式编程的基础观念，不但概念上比较熟悉，而且较容易具体表现于硬件，所以大部分的编程语言都是命令式的。
2.4 程序逻辑方法
程序逻辑的基本方法是：先给出建立程序和逻辑间联系的形式化方法，然后建立程序逻辑系统，并在此系统中研究程序的各种性质，例如，在霍尔逻辑中，程序逻辑公式的形式为{P}S{Q}。
如前所述，这类公式不能表示S的终止特性，因此霍尔逻辑是讨论程序部分正确性的逻辑。如果在霍尔逻辑系统中可以证明{P}S{Q}，同时又能证明对满足前置条件的所有输入变量程序S都终止，则称程序具有完全正确性。
在公式{P}S{Q}中逻辑表达式P和Q实际上只是当作语句S的注释使用的，对逻辑公式{P}S{Q}不能进行逻辑运算，例如蕴含公式{P1}S1{Q1}→{P2}S2{Q2}就没有意义，因此霍尔逻辑还没有彻底把程序和逻辑统一起来。解决的方法之一就是使用动态逻辑(Dynamic logic)，一种刻画自动机器的逻辑(可以理解为对计算机程序运行进行刻画的逻辑)。由于其使用经典的克里普克语义学(加标迁移系统)，可以看成是模态逻辑的一个特殊情况。其理论已经趋于成熟，本身的研究价值已经不高了。
详情访问https://en.wikipedia.org/wiki/Dynamic_logic_(modal_logic)
动态逻辑中除了通常的命题连接词(Propositionalconnectives)：┐(not非)、∨(or或)、∧(and且)、→(实质蕴涵)等，及作用于非动态变元的量词(Quantifer)：L(必然)、∈(存在于)、∃(存在一个/至少有一个)与∀(所有的/任意的)，还可以引入动态连接词(Dynamic connectives)：⇒(推出)├(推论)、⊻(xor异或)。例如{ },{S}Q表示当S终止时Q为真。这样┐{S}Q,{S1}P→{S2}Q等就都是有意义的逻辑公式，如果进一步令〈〉表示┐{ }┐，则S>Q表示存在一个时刻S终止且Q为真。程序S的部分正确性问题就可以表示为
P→{S}Q
即P真蕴含当S终止时Q为真。如果S是确定性语句，则其完全正确性问题可以表示为
P→S>Q
即P真蕴含S在某一时刻终止且Q真。
霍尔逻辑的基本思想是用逻辑描述程序的执行结果，与之对应的另一种方法是用逻辑刻画程序的全部行为，即把程序的执行过程看成机器状态的一个变化序列。自70年代中期，并发式程序设计逐渐成为程序理论的重要课题后，这种观点就显得十分必要，因为刻画在程序执行过程中，各任务之间的同步和信息交换常常是不可少的。时态逻辑是关于随着时间而不断改变其值的动态变元(叫作时序变元)的一种模态逻辑。因此它自然地被引入到程序逻辑中。时态逻辑以当前时间为基本出发点，除使用常用逻辑连接词及作用于非时序变元的量词外，还可以用引入时态连接词的办法刻画更复杂的动态性质。例如，可以引入连接词◇及□：
◇P表示在将来某一时刻P真，
□P表示P从此以后永真。
其中，(必然性)和(可能性)是模态算子，有时分别使用“L”和“M”表示这些对偶算子。
使用时态逻辑可以对每个程序构造出它所对应的一个逻辑系统，并可以在此系统中刻画终止(记作STOP)及无死锁等概念。而程序S的部分正确性问题就可以表示为
P→□(STOP →Q)
在程序S所对应的逻辑系统中成立，即程序开始执行时P真蕴含如果将来任一时刻程序终止则Q真，而其完全正确性则可表示为
P→◇(STOP&Q)
(注：HTML转义符&代替的是&，觉得这部分有错。[14])
在该逻辑系统中成立，即程序开始执行时P真蕴含存在某一时刻S终止并且Q真。
2.5 程序逻辑应用
由于程序逻辑使用逻辑系统描述程序的行为，它与具体执行程序的机器无关，因此程序逻辑的研究为公理语义学提供了理论基础。在逻辑系统中又可以分析和论证程序的性质，因此它又是程序验证的理论基础。
现代软件工程的一个重要方法是在程序设计之前，必须把程序要达到的目标即功能描述交待清楚。功能描述应当简洁明瞭，而不必关心执行细节，因此可以使用逻辑语言的全部公式。
程序设计的任务就是编制程序使其满足描述。程序逻辑的研究表明，程序和逻辑都可以作为逻辑系统的逻辑公式，所不同的是程序只出现在一部分特定的逻辑公式中。因此设计程序使之满足描述的过程，从逻辑演算角度看，就是如何将表示功能描述的逻辑公式转化成表示程序的逻辑公式问题，因此程序逻辑的研究又为软件工程中自动化设计提供了有力工具。
(注2：资料来自百度百科等[7-14]。霍尔逻辑词条认证专家为杨晓红西南大学副教授审核。词条统计：浏览8842次，编辑1次历史版本，2018-11-04最近更新：简心寂静[10]。程序逻辑词条标签：科技术语，科学。词条统计：浏览21621次，编辑6次历史版本，2016-04-25最近更新：xianjianyong99[14]。)
3. 算法逻辑的三种基本结构
算法可以理解为由基本运算及规定的运算顺序所构成的完整的解题步骤，或者看成按照要求设计好的有限的确切的计算序列，并且这样的步骤和序列可以解决一类问题。一般算法有顺序结构、选择结构、循环结构三种基本逻辑结构。
图4：算法逻辑图
中文名：算法逻辑，外文名：algorithm logic，分类：计算机编程，基本结构：顺序选择循环，常用：流程图，优势：简洁，特点：只有一个出口和入口。
3.1 算法简介
算法是完整的解题步骤或计算序列，可以解决一类问题。一般算法有顺序结构、选择结构、循环结构三种基本逻辑结构。如果用自然语言描述一个算法详细信息的话，往往过程比较复杂，缺乏简洁性，同时自然语言描述的内容可能使不同的读者产生不同的理解。因此，很有必要来探究使算法表达得更加简洁，更加直观，更加准确的方法，其中最普遍使用到的是程序流程图。
3.2 顺序结构
顺序结构是最简单的算法结构，框与框之间，语句与语句之间，都是按照它们出现的先后顺序依次进行的，即它是由若干个依次执行的处理步骤组成的。可以说顺序结构是任何一个算法都离不开的一种基本逻辑结构。
如图，其中A和B两个框是依次执行的，只有在执行完A框所指定的操作后，才能接着执行B框所指定的操作。顺序结构的一个简单的例子是交换变量a和b的值。
算法如下：
S1：m=a；S2：a=b；S1：b=m；
程序框图如图：
例：尺规作图，确定线段一个五等分点。
步骤：1、从线段的左端A点出发做一条射线；
2、在射线上取点C，得到单位线段AC；
3、在射线上做线段CE=AC；EF=AC；FG=AC；GD=AC；
4、连接DB；
5、过C做BD的平行线，交线段AB于M，即为五等分点。
3.3 选择结构
在一个算法中，经常会遇到一些条件的判断、算法的流程根据条件是否成立有不同的流向，这种先根据条件作出判断，再决定执行哪一种操作的结构称为选择结构，如下图所示的一个条件分支结构，此结构中包含一个判断框，根据给定的条件P是否成立而选择执行A框或B框，请注意，无论P条件是否成立，只能执行A框或B框之一，不可能既执行A框又执行B框，也不可能A框和B框都不执行。无论走哪一条路径，在执行完A框或B框之后，脱离本选择结构。A框或B框两个框中，可以有一个是空的，即不执行任何操作。
例：输入3个数a，b，c，要求输出最大值
步骤：
1、先比较2个数，取其中大者与第三个数比较，得出较大者为最大数，记为max
2、输入a,b,c
3、比较a，b，若a>b，则执行第三步；否则，执行第四步
4、比较a，c，若a>c，则输出最大数max=a；否则，输出最大数max=c
5、比较b，c，若b>c，则输出最大数max=b；否则，输出最大数max=c。
3.4 循环结构
需要重复执行同一操作的结构称为循环结构，即从某处开始，按照一定条件反复执行某一处理步骤，反复执行的处理步骤称为循环体。循环结构中通常都有一个起循环计数作用的变量，这个变量的取值一般都包含在执行或终止循环的条件中。循环结构有while型循环(也称当型循环)和until型循环(也称直到型循环)两种。
例：求解1到100之间所有数字之和
我们可以知道，只有在满足循环条件的情况下，才能执行循环体的操作。那么，在算法中，也会存在这种情况呢：循环条件永远满足导致循环体一直会被执行。
如果出现类似这种循环，我们称之为死循环。因为循环条件满足，则循环体会被无休止的执行下去，直到资源耗尽，那么，假若在循环结构之后还有其它的算法步骤，则没有机会被执行到。为了避免这种情况的出现，我们应该尽量在循环体中构建出能够退出循环的条件，以确保循环结构之后的算法步骤能够被执行到。当然，我们也可以在循环体中使用break,continue,return这样的跳转语句来使循环体有机会被跳出[15]。
3.5 三种结构特点
这三种基本结构的共同特点是：
1、只有一个入口和出口。
2、结构内的每一部分都有机会被执行到，也就是说对每一个框来说都应当有一条从入口到出口的路径通过它，如图中的A，没有一条从入口到出口的路径通过它，就是不符合要求的算法结构。
3、结构内不存在死循环，即无终止的循环，像右图就是一个死循环，在流程图中是不允许死循环的。
(注3：资料来自百度百科等[15-21]。本词条认证专家为肖志勇江南大学副教授审核。词条统计：浏览3090次，编辑0次历史版本，2017-07-24最近更新：馥磔。)
4. 典型算法逻辑之循环简介
循环结构是指在程序中需要反复执行某个功能而设置的一种程序结构。它由循环体中的条件，判断继续执行某个功能还是退出循环。根据判断条件，循环结构又可细分为以下两种形式：先判断后执行的循环结构(当型循环)和先执行后判断的循环结构(直到型循环)。[22]
图10：当型循环和直到型循环
循环结构可以减少源程序重复书写的工作量，用来描述重复执行某段算法的问题，这是程序设计中最能发挥计算机特长的程序结构。循环结构可以看成是一个条件判断语句和一个向回转向语句的组合。
中文名：循环结构，外文名：loop structure，减少：源程序重复书写的工作量，描述：重复执行某段算法的问题，利用：判断框来表示，编程语言：C语言，编程语言：Java语言，编程语言：Python语言。
4.1 结构简介
循环结构可以看成是一个条件判断语句和一个向回转向语句的组合。循环结构有三个要素：循环变量、循环体和循环终止条件。循环结构在程序框图中是利用判断框来表示，判断框内写上条件，两个出口分别对应着条件成立和条件不成立时所执行的不同指令，其中一个要指向循环体，然后再从循环体回到判断框的入口处。
4.2 C语言循环语句(▪三个循环▪三个循环异同点)
4.2.1 三个循环
C语言中提供goto循环、while循环、do…while循环和for循环，共四种循环。一般情况下，这四种循环可以用来处理同一问题，可以互相代替换。但一般不提倡用goto循环，因为强制改变程序的顺序经常会给程序的运行带来不可预料的错误。我们主要学习while、do…while、for三种循环。
要清楚常用的三种循环结构的相同与不同之处，以便在不同场合下使用。就这三种循环的格式和执行顺序，将每种循环的流程图理解透彻后就会明白如何替换使用，如把while循环的例题，用for语句重新编写一个程序，这样能更好地理解它们的作用。特别要注意在循环体内应包含趋于结束的语句(即循环变量值的改变)，否则就可能成了一个死循环，这是初学者的一个常见错误。
4.2.2 三个循环异同点
这三个循环的异同点：用while和do…while循环时，循环变量的初始化操作应在循环体之前，而for循环一般在语句1中进行的；while循环和for循环都是先判断表达式，后执行循环体；而do…while循环是先执行循环体后判断表达式，也就是说do…while的循环体最少被执行一次，而while循环和for就可能一次都不执行。另外还要注意的是这三种循环都可以用break语句跳出循环，用continue语句结束本次循环，而goto语句与if构成的循环，是不能用break和continue语句进行控制的。
顺序结构、分支结构和循环结构并不彼此孤立的，在循环中可以有分支、顺序结构，分支中也可以有循环、顺序结构。不管哪种结构，均可广义地看成一个语句。实际编程过程中常将这三种结构相互结合以实现各种算法，设计出相应程序。但是要编程的问题较大，编写出的程序就往往很长、结构重复多，造成可读性差，难以理解，解决这个问题的方法是将C程序设计成模块化结构。
模块化程序结构C语言的模块化程序结构用函数来实现，即将复杂的C程序分为若干模块，每个模块都编写成一个C函数，然后通过主函数调用函数及函数调用函数来实现一大型问题的C程序编写。因此常说：C程序=主函数+子函数。因此，对函数的定义、调用、值的返回等要尤其注重理解和应用，并通过上机调试加以巩固。
4.3 循环结构
当条件成立的时候，执行循环体的代码，当条件不成立的时候，跳出循环，执行循环结构后面的代码。循环结构可以减少源程序重复书写的工作量，用来描述重复执行某段算法的问题，这是程序设计中最能发挥计算机特长的程序结构。循环结构可以看成是一个条件判断语句和一个向回转向语句的组合。另外，循环结构的三个要素：循环变量、循环体和循环终止条件。循环结构在程序框图中是利用判断框来表示，判断框内写上条件，两个出口分别对应着条件成立和条件不成立时所执行的不同指令，其中一个要指向循环体，然后再从循环体回到判断框的入口处。
4.4 常见的两种循环结构
①当型循环：先判断所给条件p是否成立，若p成立，则执行A(步骤)；再判断条件p是否成立；若p成立，则又执行A，若此反复，直到某一次条件p不成立时为止。
②直到型循环：先执行A，再判断所给条件p是否成立，若p不成立，则再执行A，如此反复，直到p成立，该循环过程结束。
(注4：资料来自百度百科等[22-23]。词条标签：科学，学科。词条统计：浏览104404次，编辑23次历史版本，2018-08-30最近更新：robotwin7。[23])
5. 循环等重复类型算法程序
表示“重复”含义的计算机算法有很多，比如循环(loop)、递归(recursion)、递推(recurrence)、迭代(iterate)、遍历(traversal)等。其中，循环是最基础的概念，凡是重复执行一段代码或同一操作，都可以称之为循环。大部分递归、递推、遍历、迭代等等，都是循环，或循环为主的复杂结构。
5.1 重复类型算法：递归、递推、迭代、遍历
三种循环结构请看前面第4节。递归就是根据一种(几种)基本情况定义的算法，其他复杂情况都可以被逐步还原为该基本情况。编程中的特征是，在函数定义内重复调用该函数。具体概念如下：
递归(recursive)：从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程，称为递归。
递推(recurrence)：递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。通常是通过计算机前面的一些项来得出序列中的指定象的值。
递归与递推区别：相对于递归算法，递推算法免除了数据进出栈的过程，也就是说，不需要函数不断的向边界值靠拢，而直接从边界出发，直到求出函数值。
递归(recursive)、递推(recurrence)等基本算法思想是解决基础问题的很实用的方法。典型的递推有：简单的动态规划，根据递推公式，累加；斐波那契函数：F(n)=F(n-1)+F(n-2)，随便给一个n，问F(n)为多少。普通递归有：化解问题逐渐变小(从n到1)，例如求n的阶乘：
public staticint njiecheng(int n){
if(n==1){
return 1;
}
else {
return n*njiecheng(n-1);
}
}
又如斐波那契数列，定义F(0)=1,F(1)=1, 所有其他情况: F(x)=F(x-1)+F(x-2). 所有大于1的整数经过有限次的反推之后都可以转换到两种基本情况。而在编程中，算法则是这样的：
int F(x){
if(x==0 || x==1)
return 1; //这里是退出递归的条件, 以保证在有限次递归后能够得到结果
return F(x-1)+F(x-2); //转化为更为基本的情况, 重复调用自身进行计算
}
迭代(iterate)：在数学和编程中有不同的含义。迭代(iterate)一般适用于线性结构(数组、队列)。
迭代(数学)：在循环的基础上，每一次循环，都比上一次更为接近结果。下面是一个迭代例子：
int result = 0;
for(int i=0;i<10; i++)
result += i; //每一次循环之后, result都更加接近结果45
有很多数学问题，都是迭代算法，如牛顿迭代法(求平方根)。
迭代(编程)：按顺序访问一个列表中的每一项，在很多编程语言中表现为foreach语句：
$arr=[1, 2, 3,4];
foreach($arr as$i)
echo $i;
遍历(traversal)：按一定规则访问一个非线性的结构中的每一项，强调非线性结构(树、图)。相对来说，迭代一般适用于线性结构(数组、队列)；遍历适用于非线性结构。总体上，
· 循环(loop)- 最基础的概念, 所有重复的行为
· 递归(recursion)- 在函数内调用自身, 将复杂情况逐步转化成基本情况
· (数学)迭代(iterate)-在多次循环中逐步接近结果
· (编程)迭代(iterate)-按顺序访问线性结构中的每一项
· 遍历(traversal)- 按规则访问非线性结构中的每一项
这些都表示“重复”类型的算法彼此互相交叉，在上下文清晰的情况下，不必做过于细致的区分。
5.2 算法例1 斐波那契数列
已知f(1)=1,f(2)=1, 且满足关系式f(n)=f(n-1)+f(n-2)，则f(50)等于多少？
分析：根据初始条件f(1)=1, f(2)=1和关系式f(n)=f(n-1)+f(n-2)，可知，f(3)=f(2)+f(1),f(3)=f(2)+f(1)…….
编写代码(递归)：
public classFibonacci {
static intfun(int n){
if(n == 1 || n == 2){
return 1 ;
}else{
return fun(n-1)+ fun(n-2);
}
}
public staticvoid main(String[] args){
for(int i = 1 ; i <= 15 ; ++i){
System.out.println(fun(i));
}
}
编写代码(递推)：
static intfun2(int n){
int a[] = new int[20];
a[1] = 1 ;
a[2] = 1 ;
for(int i=3 ; i<=n ;i++){
a[i] = a[i-1] + a[i-2] ;
}
return a[n] ;
}
运行结果：
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
5.3 算法例2 使用递归计算1+2+…+100；
分析：递归关系为f(n)=f(n-1)+n，递归出口为f(1)=1;
编写代码(递归)：
public class Sum{
static int fun(int n){
if( n == 1){
return 1 ;
}else{
return fun(n-1)+ n ;
}
}
public staticvoid main(String[] args){
// TODO Auto-generated method stub
System.out.println(fun(100));
}
}
编写代码(递推)：
static intfun2(int n){
int a[] = new int[200] ;
a[1] = 1 ;
for(int i=2 ; i<=n ; i++){
a[i] = a[i-1] + i ;
}
return a[n] ;
}
运行结果：
5050
5.4 算法例3 爬楼问题
爬楼问题：假设有n阶楼梯，每次可爬1阶或2阶，则爬到第n层有几种方案？
问题分析：假设一阶时只有一种方案f(1)= 1 ; 二阶时有两种方案(即一次走一阶和一次走两阶)f(2)= 2 ;三阶时有3种 f(3)= 3 ;四阶时有五种 f(5)= 5 ;发现递归规律f(n)= f(n-1)+f(n-2); 递归出口为f(1)= 1、f(2)= 2 ;
编写代码(递归)：
public classLadder {
static int fun(int n){
if(n == 1){
return 1 ;
}else if(n == 2){
return 2 ;
}else{
return fun(n-1)+ fun(n-2);
}
}
public staticvoid main(String[] args){
// TODO Auto-generated method stub
System.out.println(fun(5));
}
}
编写代码(递推)：
static intfun2(int n){
int a[] = new int[200] ;
a[1] = 1 ;
a[2] = 2 ;
for(int i=3 ; i<=n ;i++){
a[i] = a[i-1] + a[i-2] ;
}
return a[n] ;
}
运行结果：
8
由上述例子可知，递归的重点是找到递归关系和递归出口。
5.5 算法例4 Prolog程序递归
Prolog是一门声明式编程语言，当你处理事物集合时，如列表或树，你会经常使用递归而不是迭代。Prolog递归是其中最主要而又最难于掌握的概念之一。本节选择SWI Prolog程序学习。未来学习中，如果需要控制回溯的程度，再了解一下截断这个概念(另篇介绍)。
图11：电脑安装SWI-Prolog或其他Prolog逻辑编程语言
5.5.1 牛刀小试——寻找祖先和后代的程序
①让我们先从这一个简单的例子来了解递归的性质吧。
在ancestor子句中的一个子句会使用ancestor子句。在这个例子中，ancestor(Z, Y)是一个递归的子目标。father是实现递归子目标的核心事实。规则ancestor/2有两个子句。
如果一个规则由多个子句组成，那么其中一个子句为真，则这个规则为真。可以把子句间的逗号看成是条件“与”的关系，把子句之间的句号看成是条件“或”的关系。
father(zeb, john_boy_sr).
father(john_boy_sr,john_boy_jr).
ancestor(X, Y):
father(x,y).
ancestor(X, Y):
father(X, Z), ancestor(Z, Y).
②我们可以测试一下这个规则：
我们首先询问命题ancestor(john_boy_sr,john_boy_jr).和ancestor(zeb, john_boy_jr).是否为真，接着给出变量Who，分别寻找zeb的后代和john_boy_jr的祖先。
我们已经可以在知识库中使用这个规则实现两个目的：寻找祖先和后代。
Welcome toSWI-Prolog (threaded, 64 bits, version 8.1.0-47-gc355e3712)
SWI-Prolog comeswith ABSOLUTELY NO WARRANTY. This is free software.
Please run ?-license. for legal details.
For online helpand background, visit http://www.swi-prolog.org
For built-inhelp, use ?- help(Topic). or ?- apropos(Word).
?- ancestor(john_boy_sr,john_boy_jr).
ture.
?- ancestor(zeb,john_boy_jr).
ture.
?- ancestor(zeb,who).
who= john_boy_sr;
who= john_boy_jr;
false.
?- ancestor(who,john_boy_jr).
who= john_boy_sr;
who= zeb;
false.
5.5.2 渐入佳境——利用递归计算阶乘
①一个整数的阶乘定义为，该数与小于它的全部正整数的积，一个整型数的阶乘用该数及后面的感叹号表示(!)。比如：5! = 5 × 4 ×3 × 2 × 1。一般形式为：
n! = n ×(n - 1)×(n - 2)×……× 3 × 2 × 1
然而，一个整型数的阶乘还可能表示为这个整型数与公比其小1 的那个整型数的阶乘的乘积，例如：5!=5×4!。这种阶乘的定义方式就体现了递归，因为它利用阶乘自定义阶乘。因此，任一正整数的阶乘可用下面递归定义给出：
n! = n ×(n-1)!
②在数学的定义上，0的阶乘等于1。因此，阶乘的完整定义如下：
0! = 1(停止条件)
n! = n x(n - 1)!(递归定义)
转换成Prolog程序如下图所示：
factorial(0,1). %停止条件
factorial(Num,Fact): %递归定义
Num is Num -1,
factorial(Num1, Fact1),
Fact is Num + Fact1.
③在询问后，得到结果后按回车。运行结果如图所示。值得注意的是，在知识库中停止条件应该放在递归规则前面，这一点是至关重要的。因为如果不是这样，停止条件将永远不会满足。假如把规则放在停止条件前面，那么Prolog重复进入知识库时将首先遇到它，并与其进行匹配，即使是应满足停止条件时，也绝不会与停止条件匹配，从而引起无穷递归。
Welcome toSWI-Prolog (threaded, 64 bits, version 8.1.0-47-gc355e3712)
SWI-Prolog comeswith ABSOLUTELY NO WARRANTY. This is free software.
Please run ?-license. for legal details.
For online helpand background, visit http://www.swi-prolog.org
For built-inhelp, use ?- help(Topic). or ?- apropos(Word).
?- factorial(4, Fact).
Fact=24.
?- factorial(11,Fact).
Fact=39916800.
?- factorial(0, Fact).
Fact=1.
5.5.3 趁热打铁——斐波那契数列
①数学的斐波那契数列是一个正整数数列，它与黄金比例有着密切的联系。该数列的下一个数是由其前面两个数相加得到的，头两个数均为1。该数列如下：
1，1，2，3，5，8，13，21，34，55，……
通式为：
f(1)=1(两个停止条件)
f(2)=1
f(n)=f(n-1)+f(n-2)(递归规则)
②这里用Num1、Num2这两个变量分别来表示序数Num项的前面两项；变量Term1和Term2分别表示前两项斐波那契数的结果。来转换成Prolog程序如下图所示：
fib(1, 1). %停止条件之一
fib(2, 1). %两个停止条件
fib(Num, Term):
Num1 is Num -1,
Num2 is Num -2,
fib(Num1, Term1), %递归规则之一
fib(Num2, Term2), %两个递归规则
Term is Term1+Term2.
③运行后的结果如下图所示。从截图可以看出，这些递归的程序还存在一些问题，比如在已经得出结果后，如果按“;”键试图查找另一个解时，会出现错误的答案，甚至开始报错。因为如果查找另一个结果，会重新进入递归条件，会再次减去数字，因而会报错。我将会在下次介绍Prolog的另一个机制——截断。
Welcome toSWI-Prolog (threaded, 64 bits, version 8.1.0-47-gc355e3712)
SWI-Prolog comeswith ABSOLUTELY NO WARRANTY. This is free software.
Please run ?-license. for legal details.
For online helpand background, visit http://www.swi-prolog.org
For built-inhelp, use ?- help(Topic). or ?- apropos(Word).
?- fib(10, Term).
Term = 55.
?- fib(1, Term).
Term = 1.
?- fib(2, Term).
Term = 1.
?- fib(11, Term).
Term = 89.
?- fib(4, Term).
Term = 3.
ERROR: Out of local stack
5.5.4 递归Prolog程序总结
前面的实例说明了递归的Prolog程序。递归是大多数Prolog程序中的主要控制手段。
总的来说，递归规则具有下列一般形式：
递归规则的停止条件.
递归谓词:-
某些初始计算,
递归谓词,
某些最终运算.
在编写递归程序时，应牢记下述几点：
❶所有递归规则都必须有停止条件，如果没有停止条件，递归规则将无止境地递归下去。
❷一般情况下，停止条件应该放在知识库中递归规则的上方。因为如果总找不到停止条件，也将导致无穷递归。
❸通常，在编写Prolog程序时应尽量采用递归，这要求自问如下问题：
➀是否可以把问题用其自身表达出来？
➁停止条件是什么？
5.6 算法例5 Java遍历集合的方法
Java语言中，提供了一套数据集合框架，其中定义了一些诸如List、Set等抽象数据类型，每个抽象数据类型的各个具体实现，底层又采用了不同的实现方式，比如ArrayList和LinkedList。
除此之外，Java对于数据集合的遍历，提供了几种不同的方式。开发人员必须要清楚的明白每一种遍历方式的特点、适用场合、以及在不同底层实现上的表现。下面简单分析一下。
数据元素是怎样在内存中存放的？
数据元素在内存中，主要有2种存储方式：
1、顺序存储，Random Access (DirectAccess)：
这种方式，相邻的数据元素存放于相邻的内存地址中，整块内存地址是连续的。可以根据元素的位置直接计算出内存地址，直接进行读取。读取一个特定位置元素的平均时间复杂度为O(1)。正常来说，只有基于数组实现的集合，才有这种特性。Java中以ArrayList为代表。
2、链式存储，SequentialAccess：
这种方式，每一个数据元素，在内存中都不要求处于相邻的位置，每个数据元素包含它下一个元素的内存地址。不可以根据元素的位置直接计算出内存地址，只能按顺序读取元素。读取一个特定位置元素的平均时间复杂度为O(n)。主要以链表为代表。Java中以LinkedList为代表。
1、传统的for循环遍历，基于计数器的：
遍历者自己在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后，停止。主要就是需要按元素的位置来读取元素。这也是最原始的集合遍历方法。
写法为：
for(int i = 0; i< list.size(); i++) {
list.get(i);
}
2、迭代器遍历，Iterator：
Iterator本来是OO的一个设计模式，主要目的就是屏蔽不同数据集合的特点，统一遍历集合的接口。Java作为一个OO语言，自然也在Collections中支持了Iterator模式。
写法为：
Iteratoriterator = list.iterator();
while(iterator.hasNext()){
iterator.next();
}
3、foreach循环遍历：
屏蔽了显式声明的Iterator和计数器。
优点：代码简洁，不易出错。
缺点：只能做简单的遍历，不能在遍历过程中操作(删除、替换)数据集合。
写法为：
for(ElementTypeelement : list) {
}
5.6.1 实现原理
每个遍历方法的实现原理是什么？
1、传统的for循环遍历，基于计数器的：
遍历者自己在集合外部维护一个计数器，然后依次读取每一个位置的元素，当读取到最后一个元素后，停止。主要就是需要按元素的位置来读取元素。
2、迭代器遍历，Iterator：
每一个具体实现的数据集合，一般都需要提供相应的Iterator。相比于传统for循环，Iterator取缔了显式的遍历计数器。所以基于顺序存储集合的Iterator可以直接按位置访问数据。而基于链式存储集合的Iterator，正常的实现，都是需要保存当前遍历的位置。然后根据当前位置来向前或者向后移动指针。
3、foreach循环遍历：
根据反编译的字节码可以发现，foreach内部也是采用了Iterator的方式实现，只不过Java编译器帮我们生成了这些代码。
5.6.2 算法性能
各遍历方式对于不同的存储方式，性能如何？
1、传统的for循环遍历，基于计数器的：
因为是基于元素的位置，按位置读取。所以我们可以知道，对于顺序存储，因为读取特定位置元素的平均时间复杂度是O(1)，所以遍历整个集合的平均时间复杂度为O(n)。而对于链式存储，因为读取特定位置元素的平均时间复杂度是O(n)，所以遍历整个集合的平均时间复杂度为O(n2)(n的平方)。
ArrayList按位置读取的代码：直接按元素位置读取。
transientObject[] elementData;
public E get(intindex) {
rangeCheck(index);
return elementData(index);
}
E elementData(intindex) {
return(E) elementData[index];
}
LinkedList按位置读取的代码：每次都需要从第0个元素开始向后读取。其实它内部也做了小小的优化。
transient intsize = 0;
transientNode<E> first;
transientNode<E> last;
public E get(intindex) {
checkElementIndex(index);
return node(index).item;
}
Node<E>node(int index) {
if(index <(size >> 1)) { //查询位置在链表前半部分，从链表头开始查找
Node<E> x = first;
for(inti = 0; i < index; i++)
x = x.next;
returnx;
} else { //查询位置在链表后半部分，从链表尾开始查找
Node<E> x = last;
for(int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
2、迭代器遍历，Iterator：
那么对于RandomAccess类型的集合来说，没有太多意义，反而因为一些额外的操作，还会增加额外的运行时间。但是对于Sequential Access的集合来说，就有很重大的意义了，因为Iterator内部维护了当前遍历的位置，所以每次遍历，读取下一个位置并不需要从集合的第一个元素开始查找，只要把指针向后移一位就行了，这样一来，遍历整个集合的时间复杂度就降低为O(n)；
(这里只用LinkedList做例子)LinkedList的迭代器，内部实现，就是维护当前遍历的位置，然后操作指针移动就可以了。代码：
public E next(){
checkForComodification();
if(!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public Eprevious() {
checkForComodification();
if(!hasPrevious())
throw newNoSuchElementException();
lastReturned =next =(next == null) ? last : next.prev;
nextIndex--;
returnlastReturned.item;
}
3、foreach循环遍历：
分析Java字节码可知，foreach内部实现原理，也是通过Iterator实现的，只不过这个Iterator是Java编译器帮我们生成的，所以我们不需要再手动去编写。但是因为每次都要做类型转换检查，所以花费的时间比Iterator略长。时间复杂度和Iterator一样。
使用Iterator的字节码：
Code:
0: new #16 // class java/util/ArrayList
3: dup
4: invokespecial #18 // Methodjava/util/ArrayList."<init>":()V
7: astore_1
8: aload_1
9: invokeinterface #19, 1 //InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
14: astore_2
15: goto 25
18: aload_2
19: invokeinterface #25, 1 //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
24: pop
25: aload_2
26: invokeinterface #31, 1 //InterfaceMethod java/util/Iterator.hasNext:()Z
31: ifne 18
34: return
使用foreach的字节码：
Code:
0: new #16 // class java/util/ArrayList
3: dup
4: invokespecial #18 // Method java/util/ArrayList."<init>":()V
7: astore_1
8: aload_1
9: invokeinterface #19, 1 //InterfaceMethod java/util/List.iterator:()Ljava/util/Iterator;
14: astore_3
15: goto 28
18: aload_3
19: invokeinterface #25, 1 //InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;
24: checkcast #31 // class loop/Model
27: astore_2
28: aload_3
29: invokeinterface #33, 1 //InterfaceMethod java/util/Iterator.hasNext:()Z
34: ifne 18
37: return
5.6.3 适用场合
各遍历方式的适用于什么场合？
1、传统的for循环遍历，基于计数器的：
顺序存储：读取性能比较高。适用于遍历顺序存储集合。
链式存储：时间复杂度太大，不适用于遍历链式存储的集合。
2、迭代器遍历，Iterator：
顺序存储：如果不是太在意时间，推荐选择此方式，毕竟代码更加简洁，也防止了Off-By-One的问题。
链式存储：意义就重大了，平均时间复杂度降为O(n)，还是挺诱人的，所以推荐此种遍历方式。
3、foreach循环遍历：
foreach只是让代码更加简洁了，但是他有一些缺点，就是遍历过程中不能操作数据集合(删除等)，所以有些场合不使用。而且它本身就是基于Iterator实现的，但是由于类型转换的问题，所以会比直接使用Iterator慢一点，但是还好，时间复杂度都是一样的。所以怎么选择，参考上面两种方式，做一个折中的选择。
Java的最佳实践是什么？
Java数据集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常被List接口的实现使用，用来标记该List的实现是否支持Random Access。
一个数据集合实现了该接口，就意味着它支持Random Access，按位置读取元素的平均时间复杂度为O(1)。比如ArrayList。
而没有实现该接口的，就表示不支持Random Access。比如LinkedList。
所以看来JDK开发者也是注意到这个问题的，那么推荐的做法就是，如果想要遍历一个List，那么先判断是否支持Random Access，也就是 list instanceof RandomAccess。
比如：
if(listinstanceof RandomAccess) {
//使用传统的for循环遍历。
} else {
//使用Iterator或者foreach。
}
这篇文章提醒了我不能只考虑列表的扩展元素效率，更要考虑到查找元素的效率，毕竟将数据存放到列表中，是为了方便找出他们。
5.7 循环、递归、递推之间的联系和区别
1、递归算法与循环的设计思路区别在于：函数或算法是否具备收敛性，当且仅当一个算法存在预期的收敛效果时，采用递归算法才是可行的，否则，就不能使用递归算法。
2、从理论上说，所有的递归函数都可以转换为循环函数，然而代价通常都是比较高的。
但从算法结构来说，递归声明的结构并不总能够转换为循环结构，原因在于结构的引申本身属于递归的概念，用循环的方法在设计初期根本无法实现，这就像动多态的东西并不总是可以用静多态的方法实现一样。这也是为什么在结构设计时，通常采用递归的方式而不是采用迭代的方式的原因，一个极典型的例子类似于链表，使用递归遍历及其简单，但对于内存定义(数组方式)其定义及调用处理说明就变得很晦涩，尤其是在遇到环链、图、网格等问题时，使用循环方式从描述到实现上都变得很不现实。
3、递归其实是方便了程序员难为了机器。它只要得到数学公式就能很方便的写出程序。优点就是易理解，容易编程。但递归是用栈机制实现的(c++)，每深入一层，都要占去一块栈数据区域，对嵌套层数深的一些算法，递归会力不从心，空间上会以内存崩溃而告终，而且递归也带来了大量的函数调用，这也有许多额外的时间开销。所以在深度大时，它的时空性就不好了。
循环其缺点就是不容易理解，编写复杂问题时困难。优点是效率高。运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加。
4、循环和递归的空间复杂度比较：局部变量占用的内存是一次性的，也就是O(1)的空间复杂度，而对于递归(不考虑尾递归优化的情况)，每次函数调用都要压栈，那么空间复杂度是O(n)，和递归次数呈线性关系。
5、循环和递归的本质相似性：递归程序改用循环实现的话，一般都是要自己维护一个栈的，以便状态的回溯。如果某个递归程序改用循环的时候根本就不需要维护栈，那其实这个递归程序这样写只是意义明显一些，不一定要写成递归形式。但很多递归程序就是为了利用函数自身在系统栈上的auto变量记录状态，以便回溯。原理上讲，所有递归都是可以消除的，代价就是可能自己要维护一个栈。不过很多情况下用递归还是必要的，它往往能把复杂问题分解成更为简单的步骤，而且很能反映问题的本质。
5.7.1 递归和递推的区别：
一、递归和递推有一定的相似性
这两个问题都可以描述为形式：f(n)=g(f(n-1)，…，f(0))。这是二者的共同特点。
二、递归和递推的不同点
1、从程序上看，递归表现为自己调用自己，递推则没有这样的形式。
2、递归是从问题的最终目标出发，逐渐将复杂问题化为简单问题，最终求得问题是逆向的。
递推是从简单问题出发，一步步的向前发展，最终求得问题。是正向的。
3、递归中，问题的n要求是计算之前就知道的；
递推可以在计算中确定，不要求计算前就知道n。
4、一般来说，递推的效率高于递归(当然是递推可以计算的情况下)
5.7.2 总结：
由于一切递归问题都可以转化为循环求解，因此我们可以定义广义递归：
----------------------------------------------------------------------
如果转化为循环后，需要自己维护堆栈，则仍称为是递归的。|
----------------------------------------------------------------------
在这个定义下，有些问题适用于用递归求解，如汉诺塔问题有些问题适用于用递推来做，如求满足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)
由此可见，递推的效率要高一些，在可能的情况下应尽量使用递推。但是递归作为比较基础的算法，它的作用不能忽视。所以，在把握这两种算法的时候应该特别注意。
(注5：资料来自百度百科、CSDN等[24-28]。)
免责说明：资料来自万方数据库/学报专著/逻辑学/博客园/网易/baidu/csdn等公开期刊媒体资料。文章只为学术新闻信息传播，注明出处文字参考文献可溯源。本公众号不持有任何倾向性，亦不表示认可其观点或其所述。
转载本公号文章请注明出处、作者、时间等信息，如“此文转自©公号：数据简化DataSimp，作者：秦陇纪，时间：2016.3.15Tue”字样，详情邮件咨询QinDragon2010@qq.com，转载请保留本信息。本公号保留相应版权，如有引文/译注/出处不明或遗漏/版权问题等，请给公号发留言或邮件到DataSimp@126.com。欢迎数据科学和人工智能学界、产业界同仁赐稿，投稿邮箱DataSimp@126.com，范围：AI/语言处理/数据/智能等科学技术论文。
数据DataSimp社区分享：信息与数据处理分析、数据科学研究前沿、数据资源现状和数据简化基础的科学知识、技术应用、产业活动、人物机构等信息。欢迎大家参与投稿，为数据科学技术做贡献，使国人尽快提高数据能力，提高社会信息流通效率。做事要平台，思路要跟进；止步吃住行，无力推文明。要推进人类文明，不可止步于敲门呐喊；设计空想太多，无法实现就虚度一生；工程能力至关重要，秦陇纪与君共勉之。
—END—
参考文献(2742字)
1. [德] 黑格尔，译者：梁志学．《逻辑学》．北京：人民出版社，2002：10-41．
2. 推理，《现代汉语词典第6版》第1323页．
3. 王自贵. 莱布尼茨逻辑思想研究[D]. 西南大学,2016.
4. 张文龙. 逻辑表达式的简化和转换方法的改进[J]. 上海师范大学学报(自然科学版), 2010, 39(1):56-60.
5. John F.Wakerly．数字设计 原理与实践(原书第3版)：机械工业出版社，2003
6. 最近更新：w_ou(2018-06-06). 逻辑表达式.[EB/OL], 百度百科,https://baike.baidu.com/item/%E9%80%BB%E8%BE%91%E8%A1%A8%E8%BE%BE%E5%BC%8F, 2018-06-06,visiting date: 2019-02-22.
7. C.A.R. Hoare."An axiomatic basis for computer programming". Communications of theACM, 12(10):576–585, October 1969.
8. Robert D. Tennent:"Specifying Software" (a recent textbook that includes anintroduction to Hoare logic) ISBN 0-521-00401-2
9. 宗益祥. 意识形态“再发现”：斯图亚特·霍尔的媒介批判理论的历史逻辑．《国外理论动态》，2016
10. 最近更新：简心寂静(2018-11-04).霍尔逻辑.[EB/OL], 百度百科, https://baike.baidu.com/item/%E9%9C%8D%E5%B0%94%E9%80%BB%E8%BE%91/10007845,2018-11-04, visiting date: 2019-02-24.
11. 崔文芊,王绍源.论莱布尼茨的数理逻辑成就及成因[J].江西社会科学,2013,(6):32-36.．万方数据库．http://www.wanfangdata.com.cn/details/detail.do?_type=perio&id=jxshkx201306006,2013-09-09[引用日期2017-08-26]
12. 徐华,李明. 莱布尼茨逻辑思想国内研究述评[J].沈阳工程学院学报(社会科学版),2016,(3).doi:10.13888/j.cnki.jsie(ss).2016.03.017.
13. 徐华. 莱布尼茨的符号逻辑思想研究[D]. 北京化工大学,2017.
14. 最近更新：xianjianyong99(2016-04-25). 程序逻辑.[EB/OL], 百度百科, https://baike.baidu.com/item/%E7%A8%8B%E5%BA%8F%E9%80%BB%E8%BE%91,2016-04-25, visiting date: 2019-02-22.
15. 邢世龙.浅谈算法及算法的三种基本逻辑结构[J].基础教育论坛,2009,(1):7-8. ．万方数据库．2012-05-17，引用日期2017-07-24
16. 李洪奇，刘洪，李幼铭.混沌控制反演系统构造及算法逻辑设计．《地球科学-中国地质大学学报》，2001
17. 张进.对菊池敏典算法逻辑非处理的讨论．《数据分析与知识发现》，1991
18. 谭曼琼.奇异值分解算法逻辑设计的资源优化问题研究．《湖南大学》，2011
19. 张进.联机情报检索算法逻辑树分析法．《技术与市场》，1992
20. 王国宏，苏峰，毛士艺，何友.杂波环境下基于Hough变换和逻辑的快速航迹起始算法．《系统仿真学报》，20022
21. 最近更新：yanjunmin888, 算法逻辑.[EB/OL], baidubaike,https://baike.baidu.com/item/%E7%AE%97%E6%B3%95%E9%80%BB%E8%BE%91, 2016-08-20, visitingdata: 2019-02-12.
22. 苏选良 ．管理信息系统 ：电子工业出版社 ，2003年
23. 最近更新：robotwin7(2018-08-30). 循环结构.[EB/OL], 百度百科, https://baike.baidu.com/item/%E5%BE%AA%E7%8E%AF%E7%BB%93%E6%9E%84/9845207?fr=aladdin,2018-08-30, visiting date: 2019-02-26.
24. 叶清逸. 递推与递归.[EB/OL], 网易智能, https://blog.csdn.net/u013634252/article/details/80551060, 2018-06-02, visitingdata: 2019-01-26.
25. 小小小青菜. 循环 & 递归 & 递推 之间的联系和区别.[EB/OL], csdn, https://blog.csdn.net/weixin_35909255/article/details/70738323, 2017-04-25, visitingdata:2019-01-26.
26. 黄金夫. Java遍历集合的几种方法分析(实现原理、算法性能、适用场合).[EB/OL],博客园,https://www.cnblogs.com/xyhuangjinfu/p/5429644.html, 2016-04-25, visiting date:2019-02-22.
27. Never-say-Never. 编程中，循环、迭代、遍历和递归之间的区别.[EB/OL], CSDN, https://blog.csdn.net/mad1989/article/details/8933078,2013-05-16, visiting data:2019-01-26.
28. baidujingyan. SWI-Prolog的递归.[EB/OL], baidujingyan, https://jingyan.baidu.com/article/4f7d5712099ec41a201927ed.html,2018-08-15, visiting data:2019-01-26.
x.秦陇纪．数据简化社区Python官网Web框架概述；数据简化社区2018年全球数据库总结及18种主流数据库介绍；数据科学与大数据技术专业概论；人工智能研究现状及教育应用；信息社会的数据资源概论；纯文本数据溯源与简化之神经网络训练；大数据简化之技术体系．[EB/OL]；数据简化DataSimp(微信公号)，http://www.datasimp.org，2017-06-06．
算法逻辑理论到循环、递归、递推、迭代、遍历等代码(24500字)
(附PDF发“算法逻辑循环”下载)
秦陇纪©2010-2019数据简化DataSimp
DataSimp193算法逻辑理论到循环、递归、递推、迭代、遍历等代码DS20190130WedQinDragon.docx
简介：算法逻辑理论到循环、递归、递推、迭代、遍历等代码。作者：秦陇纪。来源：万方数据库/学报专著/逻辑学/博客园/网易/baidu/csdn/数据简化社区/秦陇纪微信群聊公众号，参考文献附引文出处。下载：公号输入栏发送关键字“算法逻辑循环”或文末链接“阅读原文”可下载本文29k字13图22页PDF资料；点链接“数据简化DataSimp”关注后，菜单项有文章分类页。版权：科普文章仅供学习研究，公开资料©版权归原作者，请勿用于商业非法目的。秦陇纪2010数据简化DataSimp综合汇译编，投稿合作、转载授权/侵权、原文引文错误等请联系DataSimp@126.com沟通。主编：秦陇纪，数据简化DataSimp/科学Sciences/知识简化新媒体创立者，数据简化社区创始人，数据简化/知识简化概念和理论提出者，数据简化OS设计师/架构师，ASM/Cs/Java/Python/Prolog程序员，前英语/设计/IT教师。每天大量中英文阅读/设计开发调试/文章汇译编简化，时间精力人力有限，欢迎支持加入社区。社区：“数据简化DataSimp、科学Sciences、知识简化”新媒体聚集专业领域一线研究员；研究技术时也传播知识、专业视角解释和普及科学现象和原理，展现自然社会生活之科学面。PhDS01秦陇纪发起，期待您参与各领域；欢迎分享、赞赏、支持科普~~
Appx(1236字).数据简化DataSimp社区简介
信息社会之数据、信息、知识、理论持续累积，远超个人认知学习的时间、精力和能力。必须行动起来，解决这个问题。应对大数据时代的数据爆炸、信息爆炸、知识爆炸，解决之道重在数据简化(Data Simplification)：通过去掉重复的、错误的数据，简化减少知识、媒体、社交数据，使信息、数据、知识越来越简单，符合人与设备的负荷。(秦陇纪，2010)
数据简化DataSimp年度会议(DS2010-2019)，聚焦数据简化技术(Data Simplification Techniques)：对各类数据从采集、处理、存储、阅读、分析、逻辑、形式等方面做简化，应用于信息及数据系统、知识工程、各类数据库、物理空间表征、生物医学数据，数学统计、自然语言处理、机器学习技术、人工智能等领域。欢迎数据科学技术、简化实例相关论文投稿加入数据简化社区，参加会议出版专著。请投会员邮箱DataSimp@163.com，详情访问社区网站www.datasimp.org。填写申请表加入数据简化DataSimp社区成员，应至少有一篇数据智能、编程开发IT文章：①原创数据智能科技论文；②数据智能工程技术开源程序代码；③翻译美欧数据智能科技论文；④社区网站发帖人管理员版主志愿者义工；⑤完善黑白静态和三彩色动态社区S圈型LOGO图标。DataSimplification/Sciences/Knowledge Simplification Public Accounts——DataSimp@163.com, 2018.12.12Wed,Xi'an, Shaanxi, China.
LIFE
Life begins at the end of your comfortzone.——Neale Donald Walsch
THE DAY
The strength of purpose and the clarity ofyour vision，alongwith the tenacity to pursue it，is your underlying driver ofsuccess.——Ragy Tomas
投稿QQ群223518938数据简化DataSimp社区；技术公众号“数据简化DataSimp”留言，或(备注：姓名/单位-职务/学校-专业/手机号)加微信账号QinlongGEcai，进“数据简化DataSimp社区”投稿群或“科学Sciences学术文献”读者群等群聊。关注如下三个公众号(搜名称也行)，关注后底部菜单有文章分类页链接。
数据技术公众号“数据简化DataSimp”：
科普公众号“科学Sciences”：
社会教育知识公众号“知识简化”：
(转载请写出处：©数据简化DataSimp2010-2018汇译编，欢迎技术、传媒伙伴投稿、加入数据简化社区！“数据简化DataSimp、科学Sciences、知识简化”投稿反馈邮箱DataSimp@126.com。)
普及科学知识，分享到朋友圈
转发/留言/打赏后“阅读原文”下载PDF