什么是递归、迭代（类比解释）

递归三板斧：

1、确定函数的定义

2、确定状态转换式

3、确定边界

以二叉树的中序遍历为例：

class Solution(object):
	def inorderTraversal(self, root):
		"""
		:type root: TreeNode
		:rtype: List[int]
		"""
		res = []
		def dfs(root):
			if not root:
				return
			# 按照 左-打印-右的方式遍历	
			dfs(root.left)
			res.append(root.val)
			dfs(root.right)
		dfs(root)
		return res

1、确定函数的定义：

dfs(root) 含义是 以root为根节点的二叉树的中序遍历

2、确定状态转换式：

根据中序遍历的顺序（左根右），得到当前左子树为根节点的中序遍历（root.left），才能对当前节点进行操作，即 res.append(root.val)， 然后再对右子树进行中序遍历

3、确定边界：

显然二叉树的边界为遍历到的节点为叶子节点。

递归解释1：

递归解释2：

递归解释3：

有个朋友过来给你讲故事。

从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

--从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

----从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

------从前有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

这样下去有无数层

你终于受不了讲故事的，怒气值满了一脚把对方踢飞了，这叫做Stack Overflow，毕竟你的时间资源和耐心是有限的。

对方养好了伤之后，又来给你讲故事，这次他为了防止不会挨打，他决定有办法终止这个轮回，于是他把“从前”改为了固定年份，并且他事先声明：只讲到1513年，就终止。故事变成了：

1444年时，会有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

--1445年时，会有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

----1446年时，会有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

你耐着性子听到了后面，正想打人时：

1511年时，会有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

--1512年时，会有座山，山上有座庙，庙里有个老和尚，老和尚在给小和尚讲故事，故事讲的是

----1513年时，会有座山，但新教出现了，山上的庙改成了小教堂，

--1512年的故事讲完了

1511年的故事讲完了

你非常高兴，他一把拉住你，说还没完：

--------1510年的故事讲完了

------1509年的故事讲完了

----1508年的故事讲完了

--1507年的故事讲完了

你快发疯了，终于等到

1444年的故事讲完了

这次你没有打人。

迭代解释：

迭代就是把这次的输出作为下一次的输入

参考链接：什么是递归？ - 知乎

递归和迭代_键盘上的钢琴师_v5的博客-CSDN博客_迭代和递归的区别