从计算思维的视角辨析算法中的递归与迭代

循环（迭代）与递归的区别循环（迭代）与递归的区别转载：https:///wuxiuyong/article/details/77529401递归和迭代都是循环的⼀种。

简单地说，递归是重复调⽤函数⾃⾝实现循环。

迭代是函数内某段代码实现循环，⽽迭代与普通循环的区别是：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下⼀次循环计算的初始值。

递归循环中，遇到满⾜终⽌条件的情况时逐层返回来结束。

迭代则使⽤计数器结束循环。

当然很多情况都是多种循环混合采⽤，这要根据具体需求。

递归的例⼦，⽐如给定⼀个整数数组，采⽤折半查询返回指定值在数组中的索引，假设数组已排序，为⽅便描述，假设元素都为正数,数组长度为2的整数倍。

折半查询是查询的⼀种，⽐遍历所有元素要快很多。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15int Find(int*ary,int index,int len,int value){if(len==1)//最后⼀个元素{if(ary[index]==value)return index;//成功查询返回索引return-1;//失败，返回-1}//如果长度⼤于1，进⾏折半递归查询int half=len/2;//检查被查值是否⼤于上半部分最后⼀个值，如果是则递归查询后半部分if(value>ary[index+half-1])return Find(ary,index+half,half,value);//否则递归查询上半部分return Find(ary,index,half,value);}迭代经典例⼦就是实数的累加，⽐如计算1-100所有实数的和。

1.所谓的递归慢到底是什么原因呢？⼤家都知道递归的实现是通过调⽤函数本⾝，函数调⽤的时候，每次调⽤时要做地址保存，参数传递等，这是通过⼀个递归⼯作栈实现的。

具体是每次调⽤函数本⾝要保存的内容包括：局部变量、形参、调⽤函数地址、返回值。

递归和迭代的算法实现递归和迭代是计算机科学中常用的两种算法实现方式。

它们都可以用于解决许多问题，但是它们之间有一些不同之处。

递归算法是一种自我调用的算法，通过将问题分解为更小的子问题来解决大型问题。

递归通常使用函数或方法来实现，它们会在执行过程中多次调用自身，直到达到某个终止条件为止。

递归算法通常比较简单、易于理解和编写，但是可能会导致堆栈溢出等问题。

例如，以下是一个计算阶乘的递归函数：```def factorial(n):if n == 0:return 1else:return n * factorial(n-1)```这个函数将一个整数作为输入，并返回其阶乘。

如果输入为0，则返回1。

否则，它将调用自身来计算n-1的阶乘，并将其与n相乘。

另一方面，迭代算法是通过重复执行相同的操作来解决问题的算法。

在迭代过程中，程序会重复执行一组指令，直到达到某个终止条件为止。

与递归不同，在迭代中不会发生函数或方法的自我调用。

例如，以下是一个计算阶乘的迭代函数：```def factorial(n):result = 1for i in range(1, n+1):result *= ireturn result```这个函数使用一个循环来计算阶乘。

它将一个整数作为输入，并返回其阶乘。

在循环中，程序将从1到n迭代，并将每个数字相乘，最终得到结果。

总的来说，递归和迭代都是非常有用的算法实现方式，但是它们之间存在一些不同。

递归通常更容易理解和编写，但可能会导致堆栈溢出等问题。

迭代则更加高效，但需要更多的代码来实现。

在选择哪种算法实现方式时，应该根据具体情况进行权衡和选择。

递归和迭代的特点
递归和迭代是两种常见的编程技术，它们在解决问题和实现算法时都有各自的特点。

递归是一种通过自身不断调用自身来解决问题的方法。

它具有以下特点：
1. 简洁性：递归可以用简洁的代码表达复杂的问题，因为它利用了函数自身的定义来解决问题。

2. 可读性：递归代码通常比较容易理解，因为它遵循了一种自顶向下的方式来解决问题。

3. 递归调用：在递归过程中，函数会不断地调用自身，直到达到某个终止条件。

4. 栈的使用：递归在实现时会使用系统栈来保存调用信息，包括参数和返回地址。

迭代则是一种通过循环来重复执行一段代码的方法。

它具有以下特点：
1. 效率高：迭代通常比递归更高效，因为它不需要频繁地创建和销毁临时变量。

2. 内存消耗少：迭代不会像递归那样产生大量的栈空间消耗，因此对于处理大规模数据集更友好。

3. 控制流程清晰：迭代的控制流程更加明确，因为它是通过循环条件来控制代码的执行。

4. 适用范围广：迭代适用于各种类型的问题，无论是数值计算、数据处理还是其他领域。

总之，递归和迭代都有各自的优势和适用场景。

在选择使用哪种方法时，需要考虑问题的规模、复杂度以及对效率和内存的要求。

通常情况下，对于简单的问题，递归可能是一个直观的选择；而对于大型数据集或性能要求较高的情况，迭代可能更为合适。

迭代法、递归、递推、穷举法一、迭代法例：求两个数的最大公约数辗转相除法：用较大的数对较小的数取余数，如果余数为0那么最大公约数就是小的那个数。

如果不为0那么让除数变为较大的数，余数变为较小的数，继续这样下去直到余数为0。

var num0=Number(prompt("输入一个数"));var num1=Number(prompt("再输入一个数"));var res=maxGCD(num0,num1);alert(res);function maxGCD(x,y){var max=Math.max(x,y);var min=Math.min(x,y);while(max%min!=0){var temp=max%min;max=min;min=temp;}return min;}这个就叫迭代法：也叫辗转法。

规律：不断的用旧的值去改变新的值，直到想要得到的结果。

套路：（1）找到迭代的变量（旧的值）被除数、除数和余数（2）确定迭代的关系直接赋值（3）迭代的条件余数不等于0作业：求一个数的算术平方根(牛顿法)var num=Number(prompt("请输入一个数"));var k=1;while(Math.abs(k*k-num)>1e-9){k=(k+num/k)/2;}document.write(k);二、递推：兔子产子问题：一般来说：兔子在出生2个月后就能生崽一对兔子每个月能生出一对兔子最开始有一对刚出生的兔子假设所有的兔子都不死，问一年后多少对兔子var arr=[1,1];for(var i=2;i<12;i++){arr[i]=arr[i-1]+arr[i-2];}alert(arr[11]);对于递推，最重要的就是找到数学公式，从当前项或当前几项推出下一项。

猴子摘桃子：一个猴子，第一天摘了若干个桃子当即吃了一半不过瘾有吃了一个。

理解迭代，递归，回溯算法思想迭代：从上到下来做⼀件事情，for循环就是迭代的⼀种。

递归：⼀般我们认为递归就是迭代的⼀种。

可以重复⼀直做⼀件事，直到达到某种条件时，跳出递归。

递归的核⼼思想 1.先找递归出⼝ 2.每次递归⽅法要做什么。

回溯：其实回溯和递归很相似，都是重复做⼀件事，区别就是在递归的⽅法前加“增加操作“，⽅法后”相应减操作“。

为了更快的了解区别，还是需要例⼦。

LeetCode题给定⼀个仅包含数字2-9的字符串，返回所有它能表⽰的字母组合。

给出数字到字母的映射如下（与电话按键相同）。

注意 1 不对应任何字母。

解法思路这是个排列组合问题对吧？这个排列组合可以⽤树的形式表⽰出来；当给定了输⼊字符串，⽐如："23"，那么整棵树就构建完成了，如下：从上⾯图来看我们可以分成两步骤来解决问题：1. 先找数字。

2.从数字对应的字母数组中找字母。

3.重复步骤1，2。

这样看来我们可以⽤迭代⽅法，也可以⽤递归和回溯来解决问题。

但迭代⽤起来相对复杂，⽐较乱。

⽅法1：递归class Solution {private String[] letterMap= {" ", //0"", //1"abc", //2"def", //3"ghi", //4"jkl", //5"mno", //6"pqrs", //7"tuv", //8"wxyz" //9};///⽤迭代法思路很混乱，1.选数字 2.选数字中的字母，3 重复1.2步骤///可以⽤递归来解决，每次先选数字，然后再选字母List<String> lists = new ArrayList<>();private int slen;public List<String> letterCombinations(String digits) {slen = digits.length();if(slen == 0) return lists;char[] ch = digits.toCharArray();dfsLetter(ch, 0, "");return lists;}private void dfsLetter(char[] digits, int path, String comLetter){if(slen == path){//当前路径已经触底，所以把此组合放进数组中lists.add(comLetter);return ;}//digits[path]表⽰当前的数字，通过数字知道当前数字包含的字母长度String str = letterMap[digits[path]-'0'];for(int i=0;i<str.length();i++)//递归的关键，每次路径加1便增加⼀个字符dfsLetter(digits, path+1, comLetter + str.charAt(i));}}　注意：26⾏是递归的出⼝，递归的核⼼思想 1.先找递归出⼝ 2.每次递归⽅法要做什么。

递归和迭代法引言递归和迭代法是计算机科学中两种常用的问题解决方法。

它们可以在不同的场景下，通过不同的方式来解决复杂的问题。

本文将分别介绍递归和迭代法的概念、原理、应用以及它们之间的比较，以帮助读者更好地理解和应用这两种方法。

递归法概念和原理递归法是一种通过调用自身来解决问题的方法。

在递归问题中，将一个大规模的问题分解为一个或多个规模较小但类似的子问题，然后通过逐层调用自身来解决这些子问题，最后将子问题的解合并为原始问题的解。

递归法遵循以下原则： - 基本情况：定义一个或多个基本情况，这些情况下问题可以直接解决，不再需要继续递归调用。

- 递归关系：将原始问题分解为一个或多个更小的规模相同的子问题，并通过递归调用来解决这些子问题。

- 结束条件：当达到基本情况时，递归调用停止，问题得到解决。

递归法的本质是利用函数的调用栈结构来实现子问题的解决和合并。

通过不断地调用函数自身，每次处理一个规模更小的子问题，最终将解汇总返回给调用函数，完成对原始问题的解决。

应用场景递归法在很多问题中都有广泛的应用，例如：1.数学计算：递归可以用于计算阶乘、斐波那契数列等数学问题。

2.树和图的遍历：递归可以应用于二叉树、多叉树、图等数据结构的深度优先搜索(DFS)和广度优先搜索(BFS)。

3.排列组合问题：递归可以用于解决生成全排列、组合等问题。

4.分治法：递归可以应用于分治法中，将大问题分解为小问题，然后通过递归解决小问题，最后将子问题的解合并为原始问题的解。

优缺点递归法的优点包括： - 代码简单：递归法相比于迭代法，代码通常更加简洁易懂。

- 逻辑清晰：递归法可以直接表达问题的分解和子问题的解决过程，逻辑清晰明确。

递归法的缺点包括： - 重复计算：递归调用可能导致重复计算子问题，效率低下。

- 调用栈溢出：递归调用过多会导致函数调用栈溢出，造成程序崩溃。

- 内存消耗：递归调用需要额外的栈空间来保存每次递归调用的上下文，可能导致内存消耗过大。

循环迭代与递归在程序设计中，循环迭代和递归是两种常用的算法思想。

它们都能用来实现程序逻辑，但两者之间还是有些区别的，下面就分别来介绍一下。

1. 循环迭代循环迭代是一种基于循环结构来实现的算法思想。

在循环迭代中，重复执行相同的操作，直到满足特定的条件。

例如，计算1到100的和，可以使用循环迭代如下所示：```sum = 0for i in range(1, 101):sum += iprint(sum)```在上述代码中，使用了for循环语句来对1到100这个区间进行遍历。

每次循环将i累加到sum变量中，最终输出sum的值，即可得到1到100的和。

循环迭代的优点是代码结构简单明了，易于理解和维护。

同时循环也是一种高效的控制结构，可以有效的优化程序的性能。

2. 递归递归是一种基于函数调用来实现的算法思想。

在递归中，将复杂的问题分解为更小的问题，直到问题变得足够简单，可以被直接解决。

```def factorial(n):if n == 0 or n == 1:return 1else:return n * factorial(n-1)```在上述代码中，使用了函数factorial来计算n的阶乘。

首先进行了条件判断，当n等于0或1时，直接返回1；否则将n乘以(factorial(n-1))的值，这个过程就是递归过程。

递归的优点是能够对问题进行更深入的分析，更加灵活和高效。

同时也可以使程序结构更加简洁明了，易于维护和扩展。

3. 循环迭代和递归的比较循环迭代和递归都有各自的优点和缺点，以下是两者的比较：优点：循环迭代：当循环次数过多时，代码结构会变得复杂、难以理解。

递归：递归深度过大时，可能会导致系统栈溢出，同时在调试和维护上也会有一定的复杂度。

总之，选择使用循环迭代还是递归，需要根据实际问题场景和需求来进行选择和取舍，每种方式都有其适用范围和局限性。

递归和迭代⼀.递归（Recursion）1.递归：以相似的⽅式重复⾃⾝的过程2.递归在程序中表现为：在函数的定义中直接或间接调⽤函数⾃⾝3.递归和循环：（1）递归是有去（递去）有回（归来），因为存在终⽌条件，⽐如你打开⼀扇门还有⼀扇门，不断打开，最终你会碰到⼀⾯墙，然后返回（2）循环是有去⽆回，但可以设置终⽌条件，⽐如你打开⼀扇门还有⼀扇门，不断打开，还有门，没有终点4.递归的递去和归来：（1）递归的递去：原问题必须可以分解成若⼲个⼦问题，⽽且⼦问题须与原始问题为同样的事（相似），且规模更⼩（2）递归的归来：⼦问题的演化必须有⼀个明确的终点，否则可能导致⽆限递归（⽆终⽌条件的循环），也就是说不能⽆限制地调⽤本⾝，须有个出⼝，化简为⾮递归状况处理5.递归在函数中的具体形式：（1）必须明确终⽌条件，并给出终⽌时的处理（2）必须有间接或直接调⽤⾃⾝解决⼩规模问题的步骤def recursion(⼤规模问题)： if end_condition: #终⽌条件 end #终⽌的处理 else: recursion(⼩规模⼦问题) #调⽤⾃⾝6.递归的应⽤：（1）问题的定义是按递归定义的（Fibonacci函数，阶乘，…）；（2）问题的解法是递归的（有些问题只能使⽤递归⽅法来解决，例如，汉诺塔问题，…）；（3）数据结构是递归的（链表、树等的操作，包括树的遍历，树的深度，…）7.递归的优缺点（1）递归的优点：简洁，容易处理问题，代码可读性⾼（2）时间和空间消耗⼤8.递归式求解的基本⽅法（1）代换法1.猜对答案2.⽤数学归纳法求解常系数，并验证递归式解的正确性例：已知：T（n）= O（n lgn）则计算：（2）递归树（3）主⽅法：不是所有情况都包括⼆.迭代1.迭代：是⼀种为了逼近所需⽬标或结果，不断⽤变量的旧值递推新值的过程2.迭代在程序中的表现：函数不断调⽤原函数的返回值，3.迭代与循环，迭代和递归⼀样，也是循环的⼀种（1）循环：参与运算的变量同时是保存结果的变量（2）迭代：当前保存的结果作为下⼀次循环计算的初始值。

「疊代法」。

以確定的部分作為起始點，循序漸進推演，最後求得答案。

「疊代法」也會有無窮無盡的情況，例如以試除法建立質數，質數是越建越多；又例如微積分所學的牛頓法，遇到曲線時，小數位數是越算越多。

寫程式時經常以迴圈來實作。

因為迴圈事實上也可以用遞迴來完成，所以讀者也可以利用遞迴來實作，只不過我想大家沒必要這麼無聊。

「遞歸法」。

找出一套縮小問題範疇的規律，以此不斷縮小問題，直到能釐清細節，便可歸納答案。

「遞歸法」也會有無窮無盡的情況，例如碎形是越分越細緻。

寫程式時主要以遞迴來實作。

因為遞迴也可以用stack和迴圈來完成，所以讀者也可以利用迴圈來實作，只不過我想大家沒必要這麼累。

Iterative Method 與Recursive Method有種對立的味道：Iterative Method是針對已知，逐步累積，直至周全；Recursive是針對未知，反覆拆解，直至精細。

Collatz ConjectureCollatz Conjecture就是俗稱的「3n+1問題」，至今尚未有人能證明其正確性。

有趣的是，目前也尚未檢查出任何反例。

Iterative Method，用迴圈實作。

只要一步一步地計算，最後便能解出答案來。

1.int step(int n) // 計算出 n 收斂到 1 所經過的次數2.{3.int t; // 次數仍舊是一步一步地計算，但改為遞迴呼叫下一步，可說是吃飽太閒。

將問題反覆拆解成更小的問題。

在Collatz Conjecture 中，數字會逐步收斂──這也就是說，數字經過除以二、乘以三再加一的計算後，問題範疇就會縮小。

在這裡，我們讓數字做了一次的計算，來縮小問題。

如果就演算法的設計策略來看，這些程式碼使用了不同的策略：前面兩支程式是Iterative Method、後面一支是Recursive Method。

但以實作的角度來看，這些程式碼卻又重新分為兩種樣式：前面一支程式是迴圈、後面兩支是長得差不多的遞迴。

什么是递归和迭代？递归和迭代要怎么⽤呢？2020-02-08作为初学者的你是否对递推这个概念感觉到烧脑呢！你有没有过会这个时候，就是你感觉你这个是理解了，但是到代码中就是满头的雾⽔呢！我当初就是这样⼦，后来我慢慢理解了，我把我对这个概念理解的写在这⾥希望可以给各位初学者⼀些帮助，这是我第⼀次写博客有些不好的地⽅⼤家可以提出来⼀.递归的定义：如果⼀个对象部分的由⾃⼰组成或按照他⾃⼰定义，则我们就把他成为递归。

（简单的来说，就是反复的调⽤⾃⼰）⼆.递归函数：书上说的很复杂，我理解的就是⼀个函数在定义中循环并解决问题的，将复杂的问题给简单化了。

⽐如说3！ 3！=3*2！ 2！=2*1！1！=1 这个例⼦就是⼀直在调⽤，反复的在调⽤知道调⽤到1！时候，递归停⽌。

最后再从每⼀步递归掉⽤返回去1 1！*2 2！*3**************递归和迭代的区别1：递归是⼀直调⽤直到递归到满⾜那个条件为指，不可以⽆限制的调⽤⾃⼰，必须有个出⼝迭代则是如果那个条件为假不满⾜的情况下，他就终⽌了2：递归有⼀个缺点就是虽然他将复杂的问题给简单化了，但是他却消耗了⼤量的内存与时间，输⼊的值过⼤时她算的很慢，因为需要每次都把前⾯的算⼀遍迭代法相⽐较来说就⽐较省时间，但就是有⼀点难理解存在⼀个由旧值不断推送给新值的变量例如这个例⼦就是对递归概念的进⼀步解释#include <stdio.h>int main() //函数的主函数也就是main()函数{ int a,b; //⾸先调⽤这⼀层的函数{int x,y; //其次是这⼀层函数{int z;}}三.常见的有关递归的编程⼀.斐波那契数列 1 1 2 3 5 8 ........通过观察可得前2项不变从第3项（算第三项）起后⾯的数等于前⾯两个数之和 f(n)=f(n-1)+f(n-2)1.递归法long Fib(int n){ if(n==0) return 0; else if(n==1) return1; else return (Fib(n-1)+Fib(n-2));}2.迭代法int f0,f1,Fib,n;//上⾯有⼀段main()函数int j;long Fib(int n)//函数的定义if(n==0){ return 0{else if (n==1){return 1}for(n=1;n< j;n++){ Fib=f0+f1; f0=f1; f1=Fib;}⼆.递归母⽺/*有⼀头母⽜，它每年年初⽣⼀头⼩母⽜。