【唐叔学算法】第二天：探索递归的魅力

递归算法简介

递归算法是一种在解决问题时，将问题分解成更小的、相似的子问题来解决的方法。它是一种非常强大的编程技术，尤其适用于那些可以自然分解为相似子问题的场景。递归算法的核心思想是：问题可以分解为更小的相同问题，直到问题足够小以至于可以直接解决。

如何使用递归算法

使用递归算法时，你需要定义两个关键部分：

1. 基本情况（Base Case）：这是递归停止的条件，防止无限递归。
2. 递归步骤（Recursive Step）：这是递归调用自己的过程，每次调用都应该向基本情况靠近。

递归算法的使用场景

递归算法适用于以下场景：

• 树结构和图结构：如二叉树遍历、图的深度优先搜索（DFS）。
• 分治算法：如归并排序、快速排序。
• 动态规划问题：某些动态规划问题可以通过递归+记忆化的方式来优化。
• 数学问题：如计算阶乘、斐波那契数列等。

LeetCode递归题目解析

入门难度：二叉树的前序遍历（题号：144）

题目链接：LeetCode 144. Binary Tree Preorder Traversal

解题思路：前序遍历的顺序是：根节点 -> 左子树 -> 右子树。我们可以递归地遍历左子树和右子树。

Java代码示例：

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) return result;
        result.add(root.val);
        result.addAll(preorderTraversal(root.left));
        result.addAll(preorderTraversal(root.right));
        return result;
    }
}

中等难度：组合总和（题号：39）

题目链接：LeetCode 39. Combination Sum

解题思路：我们需要找出所有可能的组合，使得它们的和等于目标值。对于每个数字，我们可以选择包含它或不包含它，然后递归地处理剩余的数字。

Java代码示例：

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int start, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > target) break;
            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i, current, result);
            current.remove(current.size() - 1);
        }
    }
}

更多递归题目

以下是一些可以使用递归算法解答的LeetCode题目：

• LeetCode 94. Binary Tree Inorder Traversal (题号：94)
• LeetCode 102. Binary Tree Level Order Traversal (题号：102)
• LeetCode 104. Maximum Depth of Binary Tree (题号：104)
• LeetCode 200. Number of Islands (题号：200)

递归算法是一种强大且优雅的解决问题的方法，希望这篇文章能帮助你更好地理解和应用递归。记得在实际编程中，递归可能会导致栈溢出，所以合理使用递归，并考虑使用迭代或尾递归优化。