import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class RecursionExamples {
    
    // 1. 基本递归：计算阶乘
    public static long factorialBasic(int n) {
        // 基线条件
        if (n == 0 || n == 1) {
            return 1;
        }
        // 递归关系：n! = n * (n-1)!
        return n * factorialBasic(n - 1);
    }
    
    // 2. 问题递归：未优化的斐波那契数列（存在大量重复计算）
    public static long fibonacciNaive(int n) {
        if (n <= 1) {
            return n;
        }
        // 重复计算：fib(5) = fib(4) + fib(3)，而fib(4)也会计算fib(3)
        return fibonacciNaive(n - 1) + fibonacciNaive(n - 2);
    }
    
    // 3. 优化版1：记忆化递归（解决重复计算问题）
    private static Map<Integer, Long> fibCache = new HashMap<>();
    
    public static long fibonacciMemoization(int n) {
        // 基线条件
        if (n <= 1) {
            return n;
        }
        
        // 检查缓存，避免重复计算
        if (fibCache.containsKey(n)) {
            return fibCache.get(n);
        }
        
        // 递归计算并缓存结果
        long result = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);
        fibCache.put(n, result);
        return result;
    }
    
    // 4. 优化版2：尾递归（将递归调用放在函数末尾，便于编译器优化）
    public static long factorialTailRecursion(int n) {
        // 包装函数，隐藏累加器参数
        return factorialTailRecursionHelper(n, 1);
    }
    
    // 尾递归辅助函数：acc为累加器
    private static long factorialTailRecursionHelper(int n, long acc) {
        if (n == 0 || n == 1) {
            return acc;
        }
        // 递归调用在函数末尾，且结果直接返回
        return factorialTailRecursionHelper(n - 1, n * acc);
    }
    
    // 5. 递归应用：二叉树前序遍历
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
        }
    }
    
    public static void preorderTraversal(TreeNode node) {
        if (node == null) { // 基线条件：空节点
            return;
        }
        System.out.print(node.val + " "); // 访问根节点
        preorderTraversal(node.left);    // 遍历左子树
        preorderTraversal(node.right);   // 遍历右子树
    }
    
    // 6. 递归应用：数组全排列
    public static void permute(int[] arr, int start) {
        // 基线条件：起始索引等于数组长度，输出一种排列
        if (start == arr.length - 1) {
            System.out.println(Arrays.toString(arr));
            return;
        }
        
        // 递归生成所有排列
        for (int i = start; i < arr.length; i++) {
            swap(arr, start, i);          // 交换元素
            permute(arr, start + 1);      // 递归处理子数组
            swap(arr, start, i);          // 回溯：恢复原状
        }
    }
    
    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        // 阶乘测试
        System.out.println("5的阶乘：" + factorialBasic(5));
        
        // 斐波那契测试
        System.out.println("第10个斐波那契数（未优化）：" + fibonacciNaive(10));
        System.out.println("第30个斐波那契数（记忆化）：" + fibonacciMemoization(30));
        
        // 尾递归阶乘测试
        System.out.println("10的阶乘（尾递归）：" + factorialTailRecursion(10));
        
        // 二叉树遍历测试
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        System.out.print("二叉树前序遍历：");
        preorderTraversal(root);
        System.out.println();
        
        // 全排列测试
        System.out.println("数组[1,2,3]的全排列：");
        permute(new int[]{1, 2, 3}, 0);
    }
}

7. 各版本优化说明

基本递归：直接实现递归关系和基线条件，代码简洁但可能存在效率问题（如斐波那契的重复计算）。
记忆化递归：通过缓存（Map）存储已计算的子问题结果，避免重复计算，将斐波那契的时间复杂度从 O(2ⁿ) 优化为 O(n)。
尾递归优化：将递归调用放在函数末尾，并通过累加器传递中间结果，便于编译器进行尾递归消除（优化为循环），减少栈空间占用。
递归 + 回溯：如全排列实现，通过递归探索所有可能解，配合回溯（状态恢复）确保不遗漏任何情况，是组合问题的经典解法。

递归是算法设计中的重要思想，尤其适合解决具有自相似结构的问题。实际应用中，需注意通过记忆化、尾递归等方式优化性能，避免栈溢出和重复计算。当递归深度过大时，可考虑将其转换为迭代实现（如用栈模拟递归）。

递推

1. 算法定义

递推（Recurrence）是一种从已知条件出发，通过迭代逐步推导得出结果的算法策略。它基于问题的递推关系（即当前状态与前序状态的关系），从初始条件开始，按照固定规律则重复计算，直至得到目标结果。

递推与递归的核心区别：

递推：从底向上（从小到大）推导，使用迭代实现
递归：从顶向下（从大到小）分解，使用函数自我调用实现

2. 算法思路

递推算法的核心步骤：

确定初始条件：定义问题的最小规模解（如 f(0) = 0, f(1) = 1）
建立递推关系：找到第 n 项与前序项的关系（如 f(n) = f(n-1) + f(n-2)）
迭代计算：从初始条件开始，按递推关系逐步计算至目标规模

例如，计算斐波那契数列：

初始条件：f(0)=0, f(1)=1
递推关系：f(n) = f(n-1) + f(n-2)
计算过程：f(2)=f(1)+f(0)=1 → f(3)=f(2)+f(1)=2 → ... → f(n)

3. 算法复杂度

时间复杂度：O(n)，需从初始条件迭代至目标规模，每步操作常数级
最坏时间复杂度：O(n)，不受数据分布影响，始终需要完整迭代
平均时间复杂度：O(n)
空间复杂度：O(1)（优化后）或 O(n)（未优化），取决于是否存储所有中间结果

4. 优点与缺点

优点：
- 效率高，时间复杂度稳定为 O(n)
- 无递归调用开销，避免栈溢出风险
- 实现简单，逻辑直观，易于调试
- 空间可优化至 O(1)，适合大规模问题
缺点：
- 需明确递推关系，对复杂问题难以建模
- 仅适用于具有明确前序依赖关系的问题
- 无法直接处理分治类问题（如归并排序）

5. 应用场景

数学序列问题（斐波那契数列、阶乘、杨辉三角）
动态规划的迭代实现（爬楼梯、打家劫舍、最长公共子序列）
计数问题（路径计数、组合数计算）
数值计算（多项式求值、矩阵快速幂）
状态转移问题（人口增长模型、复利计算）

6. Java 实现及优化版本

import java.util.Arrays;

public class RecurrenceExamples {
    
    // 1. 基本递推：计算斐波那契数列（存储所有中间结果）
    public static long fibonacciBasic(int n) {
        if (n <= 1) {
            return n;
        }
        
        // 存储所有中间结果
        long[] dp = new long[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        // 从初始条件递推至n
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
    
    // 2. 空间优化版：斐波那契（仅保留最近两项）
    public static long fibonacciOptimized(int n) {
        if (n <= 1) {
            return n;
        }
        
        long prevPrev = 0; // f(n-2)
        long prev = 1;     // f(n-1)
        long current = 0;  // f(n)
        
        // 仅用三个变量存储状态，空间O(1)
        for (int i = 2; i <= n; i++) {
            current = prev + prevPrev;
            prevPrev = prev;
            prev = current;
        }
        return current;
    }
    
    // 3. 二维递推：计算杨辉三角
    public static int[][] yanghuiTriangle(int rows) {
        if (rows <= 0) {
            return new int[0][];
        }
        
        int[][] triangle = new int[rows][];
        // 第一行初始条件
        triangle[0] = new int[]{1};
        
        // 从第二行开始递推
        for (int i = 1; i < rows; i++) {
            triangle[i] = new int[i + 1];
            // 每行首尾元素为1
            triangle[i][0] = 1;
            triangle[i][i] = 1;
            
            // 中间元素 = 上一行相邻两元素之和
            for (int j = 1; j < i; j++) {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
        return triangle;
    }
    
    // 4. 递推应用：爬楼梯问题（每次可走1或2步，求n阶台阶的走法数）
    public static int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }
        
        int prevPrev = 1; // 1阶台阶的走法
        int prev = 2;     // 2阶台阶的走法
        
        // 递推关系：f(n) = f(n-1) + f(n-2)
        for (int i = 3; i <= n; i++) {
            int current = prev + prevPrev;
            prevPrev = prev;
            prev = current;
        }
        return prev;
    }
    
    // 5. 高阶递推：计算卡特兰数（组合数学问题）
    public static long catalanNumber(int n) {
        if (n <= 1) {
            return 1;
        }
        
        long[] catalan = new long[n + 1];
        catalan[0] = 1;
        catalan[1] = 1;
        
        // 卡特兰数递推公式：C(n) = ΣC(i)*C(n-1-i) (i=0..n-1)
        for (int i = 2; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += catalan[j] * catalan[i - j - 1];
            }
        }
        return catalan[n];
    }
    
    public static void main(String[] args) {
        // 斐波那契测试
        System.out.println("第10个斐波那契数（基本版）：" + fibonacciBasic(10));
        System.out.println("第30个斐波那契数（优化版）：" + fibonacciOptimized(30));
        
        // 杨辉三角测试
        System.out.println("杨辉三角（5行）：");
        int[][] triangle = yanghuiTriangle(5);
        for (int[] row : triangle) {
            System.out.println(Arrays.toString(row));
        }
        
        // 爬楼梯测试
        System.out.println("5阶台阶的走法数：" + climbStairs(5));
        
        // 卡特兰数测试
        System.out.println("第5个卡特兰数：" + catalanNumber(5));
    }
}

7. 各版本优化说明

基本递推：存储所有中间结果（如 fibonacciBasic），空间复杂度 O(n)，适合需要复用中间结果的场景。
空间优化：仅保留必要的前序状态（如 fibonacciOptimized 只保留最近两项），将空间复杂度从 O(n) 降至 O(1)，是递推算法的典型优化方式。
二维递推：如杨辉三角实现，使用二维数组存储多行状态，递推关系涉及上一行的多个元素，适合处理矩阵或表格类问题。
高阶递推：如卡特兰数计算，递推关系涉及多个前序状态的组合（C(n) = ΣC(i)*C(n-1-i)），需嵌套循环实现，适合复杂的组合数学问题。

递推算法是处理具有明确状态转移关系问题的高效工具，尤其在动态规划的迭代实现中应用广泛。其核心在于找到正确的递推关系，并通过空间优化减少内存开销，是算法设计中兼顾效率和可读性的优选策略。

枚举

1. 算法定义

枚举算法（Enumeration Algorithm）又称穷举算法，是一种通过系统列举问题所有可能解，并逐一验证是否符合条件，从而找到正确解的策略。它不依赖复杂的逻辑推理，而是基于 "遍历所有可能性" 的朴素思想，适合解决解空间有限且结构清晰的问题。

枚举与暴力破解的区别：

枚举：有规则地遍历解空间，通常配合剪枝优化
暴力破解：无规则地尝试，效率更低且可能重复验证

2. 算法思路

枚举算法的核心步骤：

确定解空间：明确问题可能解的范围和形式（如取值范围、组合方式）
生成候选解：按一定规则系统生成所有候选解，避免重复和遗漏
验证条件：检查每个候选解是否满足问题的约束条件
收集结果：保存符合条件的解，根据需求返回单个解或所有解

例如，求解 "百钱买百鸡" 问题（公鸡 5 文 / 只，母鸡 3 文 / 只，小鸡 1 文 / 3 只，100 文买 100 只）：

解空间：公鸡 0-20 只，母鸡 0-33 只，小鸡 = 100 - 公鸡 - 母鸡
验证条件：5× 公鸡 + 3× 母鸡 + 小鸡 / 3 = 100 且小鸡能被 3 整除
遍历所有可能组合，筛选出符合条件的解

3. 算法复杂度

时间复杂度：O(N)，其中 N 为解空间大小，最坏可达 O(2ⁿ) 或 O(n!)（如全组合问题）
最坏时间复杂度：O(N)，需遍历全部解空间
平均时间复杂度：O(N/2)，通常需遍历一半左右的解空间
空间复杂度：O(1) 或 O(k)（k 为解的数量），仅需存储当前候选解和结果

4. 优点与缺点

优点：
- 实现简单，逻辑直观，易于理解和编码
- 只要解存在，理论上一定能找到（完备性）
- 适合解决逻辑复杂但解空间小的问题
- 无需复杂的数学推导或数据结构支持
缺点：
- 时间复杂度高，解空间大时效率极低
- 不适合大规模问题（如 n > 20 的组合问题）
- 盲目性强，缺乏智能优化（未剪枝时）
- 重复计算多，资源利用率低

5. 应用场景

小规模组合问题（如密码破解、彩票号码组合）
约束条件简单的决策问题（如百钱买百鸡、鸡兔同笼）
验证性问题（如判断某数是否为素数、寻找指定范围内的水仙花数）
作为复杂算法的辅助手段（如回溯法的基础遍历逻辑）
调试和验证（用于验证其他算法的正确性）

6. Java 实现及优化版本

import java.util.ArrayList;
import java.util.List;

public class EnumerationExamples {
    
    // 1. 基本枚举：判断素数（检查所有可能因子）
    public static boolean isPrimeBasic(int num) {
        if (num <= 1) return false;
        // 基本枚举：检查2到num-1的所有可能因子
        for (int i = 2; i < num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    // 2. 优化版1：范围缩减（素数判断）
    public static boolean isPrimeOptimized(int num) {
        if (num <= 1) return false;
        if (num == 2) return true;
        if (num % 2 == 0) return false;
        
        // 优化1：仅检查到sqrt(num)
        // 优化2：仅检查奇数（跳过偶数）
        for (int i = 3; i <= Math.sqrt(num); i += 2) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    
    // 3. 枚举应用：寻找水仙花数（三位数，各位立方和等于自身）
    public static List<Integer> findNarcissisticNumbers() {
        List<Integer> result = new ArrayList<>();
        // 明确解空间：100-999的三位数
        for (int num = 100; num < 1000; num++) {
            int hundreds = num / 100;
            int tens = (num / 10) % 10;
            int units = num % 10;
            
            // 验证条件
            if (hundreds*hundreds*hundreds + tens*tens*tens + units*units*units == num) {
                result.add(num);
            }
        }
        return result;
    }
    
    // 4. 优化版2：多重循环剪枝（百钱买百鸡问题）
    public static void hundredMoneyHundredChickens() {
        // 问题：公鸡5文，母鸡3文，小鸡1文3只，100文买100只
        // 解空间优化：
        // 公鸡最多20只（5×20=100），母鸡最多33只（3×33=99）
        for (int cock = 0; cock <= 20; cock++) {
            for (int hen = 0; hen <= 33; hen++) {
                int chick = 100 - cock - hen;
                
                // 剪枝条件1：小鸡数量不能为负
                if (chick < 0) continue;
                
                // 剪枝条件2：总钱数必须为100，且小鸡数量能被3整除
                if (5*cock + 3*hen + chick/3 == 100 && chick % 3 == 0) {
                    System.out.printf("公鸡%d只，母鸡%d只，小鸡%d只\n", cock, hen, chick);
                }
            }
        }
    }
    
    // 5. 优化版3：有序枚举避免重复（组合求和）
    // 寻找所有和为target的k个不同正整数组合（数字递增，避免重复）
    public static List<List<Integer>> combinationSum(int k, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), k, target, 1);
        return result;
    }
    
    // 有序枚举+回溯剪枝
    private static void backtrack(List<List<Integer>> result, List<Integer> temp, 
                                int k, int remain, int start) {
        // 基线条件
        if (temp.size() == k) {
            if (remain == 0) {
                result.add(new ArrayList<>(temp));
            }
            return;
        }
        
        // 有序枚举：从start开始，避免重复组合（如[1,2]和[2,1]）
        for (int i = start; i <= remain; i++) {
            // 剪枝：剩余数字不足以凑齐k个
            if (remain - i < (k - temp.size() - 1) * (i + 1)) {
                break;
            }
            
            temp.add(i);
            backtrack(result, temp, k, remain - i, i + 1); // 下一个数字必须更大
            temp.remove(temp.size() - 1); // 回溯
        }
    }
    
    public static void main(String[] args) {
        // 素数判断测试
        System.out.println("17是否为素数（基本版）：" + isPrimeBasic(17));
        System.out.println("997是否为素数（优化版）：" + isPrimeOptimized(997));
        
        // 水仙花数测试
        System.out.println("三位数水仙花数：" + findNarcissisticNumbers());
        
        // 百钱买百鸡测试
        System.out.println("百钱买百鸡的解：");
        hundredMoneyHundredChickens();
        
        // 组合求和测试：寻找3个不同正整数，和为9
        System.out.println("3个不同正整数和为9的组合：" + combinationSum(3, 9));
    }
}

7. 各版本优化说明

基本枚举：无优化地遍历全部解空间（如 isPrimeBasic 检查到 num-1），实现简单但效率低，适合理解基本原理。
范围缩减优化：通过数学分析缩小遍历范围（如 isPrimeOptimized 仅检查到 sqrt(num) 且跳过偶数），将时间复杂度从 O(n) 降至 O(√n)。
多重循环剪枝：在多层循环中添加条件判断（如百钱买百鸡问题中的 chick < 0 和 chick % 3 == 0），提前过滤无效候选解，减少计算量。
有序枚举去重：如组合求和问题中，通过强制数字递增（i + 1 作为下一轮起点）避免重复组合，比无序枚举后去重更高效。

枚举算法是解决小规模问题的实用工具，其核心优化思路是合理缩减解空间和提前剪枝。在实际应用中，枚举常作为基础策略与其他算法结合（如枚举 + 回溯、枚举 + 动态规划），在保证正确性的前提下提升效率。当问题规模较小时，枚举算法的简单性往往比效率更重要。

递归与递推

函数式编程（FP） “递归”（recursive）包含了“递推”（recurrence）和“回归”（regression）的过程，

“递归”（recursive）指的是一种方法，把大的复杂的问题分解成更小更简单的问题，逐级分解下去，直到问题的规模小到可以直接求解，然后再逐级向上回溯直到解决最初的问题，用程序来实现这种算法的时候至少包含一次以上的递推执行过程，效率当然比不上直接作一次迭代。

递归的计算过程（recursive process）包含了两个阶段，先逐级扩展（expansion），构造起一个由被推迟的操作组成的链条（会被解释器保存在堆栈里），然后在收缩（contraction）阶段逐级回溯执行那些操作。

随着递归计算步骤的增多，这种方法消耗的资源会越来越大，而且会包含越来越多的冗余操作，上面那个求斐波那契数列的例子（在SICP里被称作“树形递归”）在这方面问题尤其严重，因为它的计算步骤会随着参数而指数性的增长。

迭代（iterative）

递推与递归

思维要点

不要人肉进行递归（最大误区）
找到最近最简单方法，将其拆解成可重复解决的问题(重复子问题)
数学归纳法思维