递归、迭代、回溯、广度和深度优先

在学习算法的时候，经常碰到递归、迭代、回溯、广度优先和深度优先算法，可是回溯使用了递归，深度优先也使用了递归，广度优先有是迭代，它们之间是什么关系呢。

通过几道练习题，我们可以很发现，递归和迭代是基本的算法技巧，回溯是建立在递归之上的算法思想，而广度优先和深度优先是针对图、树的特殊递归和迭代算法。

迭代和递归

在反转链表一文中，有个结论是凡是用递归完成都可以用迭代完成，反之亦然。而递归使用了操作系统栈，这个栈有限制，所以在没有尾递归优化的语言里，要慎用递归，如果可以使得表达更符合人类思考，且不会导致栈溢出，则递归也不是一定不可以用的。

例如中序遍历，使用递归是最符合人的思考理解的：

   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

熟悉模版，怎么都非常好写出来。

小结

递归和迭代，是最基本的算法技巧，需要熟练掌握，写迭代是要牢记是自己去实现栈。而回溯算法则是针对遍历这种场景，基于迭代的一种算法思想。广度优先和深度优先是针对图的特殊搜索算法。可以说，递归和迭代是基础本质，其它都是在某场景、数据结构下具体派生产物。