递归和迭代的区别

大家好，欢迎来到IT知识分享网。

最近刷题经常会碰到迭代或递归解法，容易混淆，搜索整理如下

1、含义不同

递归是重复调用函数自身实现循环。遇到满足终止条件的情况时逐层返回来结束

迭代是函数内某段代码实现循环，循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。迭代则使用计数器结束循环。

2、结构不同

递归与迭代都是基于控制结构，都涉及重复结构

迭代用重复结构，迭代显式使用重复结构

递归用选择结构，递归通过重复函数调用实现重复

3、终止条件不同

迭代在循环条件失败时终止，迭代一直修改计数器，直到计数器值使循环条件失败；

递归在遇到基本情况时终止，使用计数器控制重复的迭代和递归都逐渐到达终止点（递归不断产生最初问题的简化副本，直到达到基本情况。）

4、基础案例：反转链表（leetcode链接）

迭代解法：

class Solution: def reverseList(self, head: ListNode) -> ListNode: # pre:前节点 # cur:当前节点 pre = None #标记前置空节点 cur = head #标记链表起始位置 while cur is not None: #当当前节点有nexc值时候 next=cur.next #临时参数next存储cur的后置 cur.next=pre #把cur的指向改为向前 pre=cur #把pre赋值为cur的值（pre后移） cur=next #把cur赋值为next的值（cur后移） return pre #返回pre（头节点）

递归解法：

def reverseList(self, head: ListNode) -> ListNode: if head is None or head.next is None: #判断是否为终止条件，如果不是执行下方替换 return head pre = self.reverseList(head.next) head.next.next = head head.next = None return pre