2.1 递归算法

2.1.1 什么是递归算法

递归是一种通过在算法的执行过程中自我调用的方式来解决问题的方法。在递归算法中，问题被分解为更小的子问题，并通过递归调用相同的算法来解决这些子问题。递归算法通常通过定义一个或多个基本情况（边界条件）来终止递归过程

这样描述可能有点抽象，下面通过几道例题进行加深你的理解。

2.1.2 递归的适用场景 递归算法适用于：

问题可以被分解为更小的子问题进行求解的场景 一些常见的应用场景包括：

树的遍历： 二叉树的前序、中序和后序遍历就是递归算法的经典示例。 图的搜索： 图的深度优先搜索（DFS）和广度优先搜索（BFS）都可以使用递归算法实现。 动态规划： 在动态规划问题中，递归算法通常被用来定义子问题的状态转移方程。 分治算法： 分治算法将问题拆分为更小的子问题，通常通过递归算法来解决。 回溯算法： 在回溯算法中，递归算法用于在解空间中搜索所有可能的解。

递归模板：

void func() {
    if (true) { // 递归结束条件
        return // 递归出口
    }
    func(); // 调用自身
}

2.1.3 递归详解

• 递归其实是一个相同方法栈，只不过方法的参数不一样
• 最开始进来的方法压在栈底，接着不断调用自身，即往栈中不断加入方法。
• 直到遇到递归出口时，最上面的方法从栈中弹出，然后进行上一个方法的计算，重复执行，直到栈为空。

请看以下例题加深理解。

2.1.3.1 剑指offer.6 从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：

输入：head = [1,3,2] 输出：[2,3,1]

分析：

从尾到头进行遍历，必须要找到尾结点，但是尾节点并没有指向上一个节点的指针，所以需要保存所有节点的指针，或者将链表反转再进行遍历。 则我们有以下解决方案：

将指针/数据存到一个数组/栈中，然后遍历数组/栈。时间复杂度O(n）, 空间复杂度O(n）。且需要遍历两次。 将链表反转再进行遍历，时间复杂度O(n）, 空间复杂度O(1)，但需要遍历两次。 利用递归性质，时间复杂度O(n）, 方法空间复杂度O(1)，栈空间复杂度O(n)。 如何用递归性质：

每次打印过程是一样的（最小子问题）。 需要保存所有节点的指针，递归方法栈自动帮我们存储。 从尾到头打印，尾部即是栈顶。

递归解法：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode(int x) { val = x; }
 * }
 */
class Solution {
    private int[] res; // 结果数组
    public int[] reversePrint(ListNode head) {
        int len = 0;  // 链表长度
        func(head, len); // 递归
        return res;
    }
    private void func(ListNode head, int len) {
        if (head == null) {
            res = new int[len]; // 在递归出口初始化结果数组，因为在这才直到链表的长度。
            return;
        }
        // 最小子问题
        len ++; // 每递归一次长度加1
        func(head.next, len);
        res[res.length-len] = head.val;
    }
}

2.1.3.2 DFS深度优先算法-树的遍历

DFS深度优先算法是树的常用遍历算法，由于树是高度递归的，所以DFS深度优先算法常用递归来实现，也可以使用栈来实现深度优先算法。

这里可以让你更加明白为啥递归是一个隐式方法栈。

DFS深度优先算法模板-递归实现：

// 先序遍历
public static void dfSPre(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历节点
    process(treeNode)
    // 遍历左节点
    dfSPre(treeNode.left);
    // 遍历右节点
    dfSPre(treeNode.right);
}
// 后序遍历
public static void dfSPost(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历左节点
    dfSPost(treeNode.left);
    // 遍历右节点
    dfSPost(treeNode.right);
    // 遍历节点
    process(treeNode)
}
// 中序遍历
public static void dfSInner(Node treeNode) {
    if (treeNode == null) {
        return;
    }
    // 遍历左节点
    dfSInner(treeNode.left);
    // 遍历节点
    dfSInner(treeNode)
    // 遍历右节点
    dfSInner(treeNode.right);
}

DFS深度优先算法模板-非递归实现：

/**
 * 使用栈来实现 dfs
 * @param root
 */
public static void dfsWithStack(Node root) {
    if (root == null) {
        return;
    }

    Stack<Node> stack = new Stack<>();
    // 先把根节点压栈
    stack.push(root);
    while (!stack.isEmpty()) {
        Node treeNode = stack.pop();
        // 遍历节点
        process(treeNode)

        // 先压右节点
        if (treeNode.right != null) {
            stack.push(treeNode.right);
        }

        // 再压左节点
        if (treeNode.left != null) {
            stack.push(treeNode.left);
        }
    }
}

补充：BFS

/**
 * 使用队列实现 bfs
 * @param root
 */
private static void bfs(Node root) {
    if (root == null) {
        return;
    }
    Queue<Node> stack = new LinkedList<>();
    stack.add(root); //根结点入队

    while (!stack.isEmpty()) {
        Node node = stack.poll(); // 头结点出队
        System.out.println("value = " + node.value); // 对结点的操作
        Node left = node.left;
        if (left != null) { // 头结点的左子树入队
            stack.add(left);
        }
        Node right = node.right;
        if (right != null) { // 头结点的右子树入队
            stack.add(right);
        }
    }
}

树的高度递归体现在：

• 对于一棵树，可分为若干个子问题，**该子问题为：**对于根结点的处理，递归到左子树进行处理，递归到右子树进行处理。
• 因此在处理树的问题且带有递归性质时，都是基于以上的思想去解决的。

2.1.3.3 leetcod 437. 路径总和 III - 路径问题通解

给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8 输出：3 解释：和等于 8 的路径有 3 条，如图所示。

分析，利用树的高度递归性：

对于一棵树，可分为若干个子问题，**该子问题为：对于根结点的处理，递归到左子树进行处理，递归到右子树进行处理 对于路径问题，我们需要记录之前路径的值。 其子问题简化为：

以当前结点为父结点 对左子树进行处理，计算左子树某条路径的值和加上父节点的值是否等于taget。 对右子树进行处理，计算右子树某天路径的值和加上父节点的值是否等于taget

代码实现

// 双递归解法，pathSum用于当前节点的遍历，func获取该结点路径。
class Solution {

    private int res;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        func(root, (double) targetSum);
        pathSum(root.left, targetSum); 
        pathSum(root.right, targetSum);
        return res;
    }
    // 先序遍历获取从根到叶节点的路径。
    private void func(TreeNode root, double targetSum) {
        if (root == null) { // 递归出口
            return;
        }
        if (targetSum-(double) root.val == 0) res++; // 根节点处理
        func(root.left, targetSum-root.val); // 递归到左子树处理
        func(root.right, targetSum-root.val); // 递归到右子树处理
    }
}

值得注意的是，递归算法性能大多数时候是极差的。leetcod 437. 路径总和 III 解析，当我们以10为根结点向下遍历时，5->3,5->2的信息我们已经计算过了，然而在递归到以10为根结点时，我们又计算了一遍，因此递归带来的时很多的重复计算的问题，且由于隐式栈的原因，很难进行优化，所以性能极差，因此在实际开发中不要应避免使用递归算法（递归算法可用栈来替代）。