如何在算法中设计递归

在算法中，有很多题都可以用递归来解决。但每次使用递归就感觉比较抽象。

什么是递归

递归就是把请解问题的过程最小单元化，每个单元又包含其子单元，通过计算机函数的可复用性，来求解问题。

完成一个递归需要哪些条件

找到这个求解单元
找出递归的退出条件

1检查边界条件 2一开始就明确最终的那个递归退出条件 3找到递归的执行单元。

比如求二叉树的最大深度

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init() { self.val = 0; self.left = nil; self.right = nil; }
 *     public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
 *     public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
 *         self.val = val
 *         self.left = left
 *         self.right = right
 *     }
 * }
 */

class Solution {
    func maxDepth(_ root: TreeNode?) -> Int {

        //检查边界条件
        // if root == nil {
        //     return 0
        // }
        //这里和最终结果一样了，故省去。


        //最终结果就是传入root为nil，就不会计算了
        guard  let root = root else {
            return 0
        }
        //每一次的单元就是找到左右两边的最大的值，加上1的深度。这里的精髓是在这个+1上，这就保证了我们每递归一次，会累加一次二叉树的深度
        return max(maxDepth(root.left), maxDepth(root.right)) + 1

    }
}