在学习算法的时候，经常碰到递归、迭代、回溯、广度优先和深度优先算法，可是回溯使用了递归，深度优先也使用了递归，广度优先有是迭代，它们之间是什么关系呢。
通过几道练习题，我们可以很发现，递归和迭代是基本的算法技巧，回溯是建立在递归之上的算法思想，而广度优先和深度优先是针对图、树的特殊递归和迭代算法。
迭代和递归
在反转链表一文中，有个结论是凡是用递归完成都可以用迭代完成，反之亦然。而递归使用了操作系统栈，这个栈有限制，所以在没有尾递归优化的语言里，要慎用递归，如果可以使得表达更符合人类思考，且不会导致栈溢出，则递归也不是一定不可以用的。
例如中序遍历，使用递归是最符合人的思考理解的：
def inorderTraversal(self, root):
if not root: return []
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right)
迭代的写法，就是放弃使用操作系统栈，而自己去构造栈，是比较难思考的，而有人给了一种color的解法，使用了迭代，而且也符合人的思考过程
def inorderTraversal(self, root: TreeNode) -> List[int]:
white, gray = 0, 1
res = []
stack = [(white, root)]
while stack:
color, node = stack.pop()
if not node:
continue
if color == white:
stack.append((white, node.right))
stack.append((gray, node))
stack.append((white, node.left))
else:
res.append(node.val)
return res
回溯算法
回溯算法就是建立在递归技巧上的，一般用于遍历。例如“给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。”
这道题使用回溯算法是最直接的算法，对于1..n的数字，每个数字选或者不选，复杂度是O(2^n)。
def combine(self, n: int, k: int) -> List[List[int]]:
self.r, self.n = [], n
self.backTracking(1, k, [])
return self.r
def backTracking(self, element: int, length: int, array: List[int]):
if not length:
self.r.append(array)
return
if element > self.n: return
self.backTracking(element + 1, length, array)
self.backTracking(element + 1, length - 1, array + [element])
这道题还可以用递归、迭代、动态规划等方法。
广度优先和深度优先
广度优先和深度优先，是针对图、树（树是一种特殊的图）的搜索算法，算法复杂度是O(n)。深度优先就是基于递归的技巧，而广度优先则是基于迭代的技巧，但是由于可以记忆标准模版，因此训练熟悉以后比较容易写出。这里的比较容易是相对于在非图中的迭代技巧写算法。
例如“给定一个二叉树，找出其最大深度。”
使用深度优先算法：
def maxDepth_recursion(self, root):
if not root: return 0
l = self.maxDepth_iteration(root.left)
r = self.maxDepth_iteration(root.right)
return 1 + max(l, r)
使用广度优先算法：
def maxDepth_bfs(self, root):
if not root: return 0
queue, r = [root], 0
while queue:
newqueue = []
r += 1
for node in queue:
if node.left:
newqueue.append(node.left)
if node.right:
newqueue.append(node.right)
queue = newqueue
return r
熟悉模版，怎么都非常好写出来。
小结
递归和迭代，是最基本的算法技巧，需要熟练掌握，写迭代是要牢记是自己去实现栈。而回溯算法则是针对遍历这种场景，基于迭代的一种算法思想。广度优先和深度优先是针对图的特殊搜索算法。可以说，递归和迭代是基础本质，其它都是在某场景、数据结构下具体派生产物。
