首页 > 其他分享 >对递归的深度理解及详细示例

对递归的深度理解及详细示例

时间:2024-07-19 09:54:33浏览次数:12  
标签:return 递归 示例 factorial result 深度 permute

文章目录


理解递归可以是一个挑战,但通过一些系统的方法,你可以逐步掌握它。以下是一些帮助你理解递归的策略和步骤:

1. 理解递归的基本概念

递归的基本思想是一个函数调用自身来解决一个更小的相同问题,直到达到基准情况(递归出口),在这个情况下不再进行递归调用。

2. 识别递归的三个关键部分

  • 基准情况(Base Case):递归什么时候停止。
  • 递归步骤(Recursive Step):函数如何分解问题并递归调用自身。
  • 组合结果(Combining Results):如何组合递归调用的结果来解决原问题。

3. 逐步分析递归函数

通过逐步分析每个递归调用,你可以更好地理解递归的执行流程。让我们用一个经典的例子:计算阶乘。

public int factorial(int n) {
    if (n == 0) { // 基准情况
        return 1;
    } else {
        return n * factorial(n - 1); // 递归步骤
    }
}
分析
  • 基准情况n == 0 时返回 1。
  • 递归步骤n * factorial(n - 1)
  • 组合结果:每次递归调用结果与当前 n 相乘。

4. 手动模拟递归调用

用纸和笔手动模拟递归调用的过程。假设 n = 3,来看 factorial(3) 的调用过程:

  1. factorial(3)
    • 3 * factorial(2)
      • 2 * factorial(1)
        • 1 * factorial(0)
          • 返回 1
        • 返回 1 * 1 = 1
      • 返回 2 * 1 = 2
    • 返回 3 * 2 = 6

最终结果是 6。

5. 可视化递归

使用递归树来可视化递归调用。每个节点表示一次递归调用。对于 factorial(3),递归树如下:

factorial(3)
  |
  3 * factorial(2)
       |
       2 * factorial(1)
            |
            1 * factorial(0)
                 |
                 1

6. 调试和打印

在递归函数中添加打印语句,跟踪每次递归调用的输入和输出。例如:

public int factorial(int n) {
    System.out.println("Entering factorial with n = " + n);
    if (n == 0) {
        System.out.println("Base case reached with n = " + n);
        return 1;
    } else {
        int result = n * factorial(n - 1);
        System.out.println("Returning " + result + " for factorial of " + n);
        return result;
    }
}

7. 从简单的递归问题开始

从简单的问题开始,比如计算阶乘、斐波那契数列、字符串反转,然后逐步解决复杂的问题,如二叉树遍历、动态规划问题。

8. 理解递归与迭代的关系

理解如何将递归转换为迭代(或相反)有助于理解递归。通过将递归函数转换为迭代版本,你可以更好地理解递归的本质。

9. 练习

通过反复练习各种递归问题,加深对递归的理解。比如二叉树遍历、汉诺塔问题、八皇后问题等。

示例 1:递归实现二叉树的后序遍历

以下是二叉树的后序遍历的递归实现,通过逐步解释每次递归调用,帮助理解递归过程:

private void postOrder2(Node node, List<T> list){
    if (node == null){
        return; // 基准情况
    }
    postOrder2(node.left, list); // 遍历左子树
    postOrder2(node.right, list); // 遍历右子树
    list.add(node.value); // 处理当前节点
}

public List<T> postOrder2(){
    LinkedList<T> list = new LinkedList<>();
    postOrder2(root, list); // 从根节点开始递归
    return list; // 返回结果列表
}
分析

对于一个二叉树:

        A
       / \
      B   C
     / \   \
    D   E   F

递归调用过程:

  1. postOrder2(A, list)
  2. postOrder2(B, list)
  3. postOrder2(D, list) -> 基准情况,返回。
  4. postOrder2(E, list) -> 基准情况,返回。
  5. 处理 B,添加 B 的值。
  6. postOrder2(C, list)
  7. postOrder2(F, list) -> 基准情况,返回。
  8. 处理 C,添加 C 的值。
  9. 处理 A,添加 A 的值。

最终结果是 [D, E, B, F, C, A]

通过这些方法和练习,你可以逐步掌握递归的概念和应用。

当然,这里有一些经典的递归示例,这些例子将帮助你加深对递归的理解:

示例 2:斐波那契数列

斐波那契数列是一个著名的递归问题,其中每个数是前两个数之和。数列的前两项通常定义为 0 和 1。

public int fibonacci(int n) {
    if (n <= 1) { // 基准情况
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2); // 递归步骤
}
分析

对于 fibonacci(4)

  1. fibonacci(4)
    • fibonacci(3) + fibonacci(2)
      • (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
        • ((fibonacci(1) + fibonacci(0)) + 1) + (1 + 0)
          • ((1 + 0) + 1) + 1
    • 最终结果为 3。

示例 3:字符串反转

反转一个字符串可以通过递归实现。

public String reverse(String str) {
    if (str.isEmpty()) { // 基准情况
        return str;
    }
    return reverse(str.substring(1)) + str.charAt(0); // 递归步骤
}
分析

对于 reverse("abc")

  1. reverse("abc")
    • reverse("bc") + "a"
      • (reverse("c") + "b") + "a"
        • (reverse("") + "c") + "b" + "a"
          • ("c") + "b" + "a"
    • 最终结果为 “cba”。

示例 4:汉诺塔问题

汉诺塔问题是一种经典的递归问题,要求将 n 个盘子从源柱移动到目标柱,辅助柱作为中间步骤。

public void hanoi(int n, char from, char to, char aux) {
    if (n == 1) { // 基准情况
        System.out.println("Move disk 1 from " + from + " to " + to);
        return;
    }
    hanoi(n - 1, from, aux, to); // 递归步骤
    System.out.println("Move disk " + n + " from " + from + " to " + to);
    hanoi(n - 1, aux, to, from);
}
分析

对于 hanoi(2, 'A', 'C', 'B')

  1. hanoi(2, 'A', 'C', 'B')
    • hanoi(1, 'A', 'B', 'C')
      • Move disk 1 from A to B
    • Move disk 2 from A to C
    • hanoi(1, 'B', 'C', 'A')
      • Move disk 1 from B to C
    • 最终结果为:
      Move disk 1 from A to B
      Move disk 2 from A to C
      Move disk 1 from B to C
      

示例 5:二叉树的最大深度

计算二叉树的最大深度(或高度)。

public int maxDepth(TreeNode root) {
    if (root == null) { // 基准情况
        return 0;
    }
    int leftDepth = maxDepth(root.left); // 递归步骤
    int rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1; // 组合结果
}
分析

对于以下二叉树:

        1
       / \
      2   3
     / \
    4   5
  1. maxDepth(root)
    • maxDepth(2), maxDepth(3)
      • maxDepth(4), maxDepth(5), 0
        • 0, 0
      • 1, 1
    • 2, 1
    • 3

最终结果为 3。

示例 6:全排列

生成一个集合的所有排列。

public void permute(List<Integer> nums, int start, List<List<Integer>> result) {
    if (start == nums.size() - 1) { // 基准情况
        result.add(new ArrayList<>(nums));
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        Collections.swap(nums, start, i);
        permute(nums, start + 1, result); // 递归步骤
        Collections.swap(nums, start, i);
    }
}

public List<List<Integer>> permute(List<Integer> nums) {
    List<List<Integer>> result = new ArrayList<>();
    permute(nums, 0, result);
    return result;
}
分析

对于 permute([1, 2, 3])

  1. 初始调用 permute([1, 2, 3], 0, result)
  2. swap(0, 0) -> permute([1, 2, 3], 1, result)
    • swap(1, 1) -> permute([1, 2, 3], 2, result)
      • 基准情况,添加 [1, 2, 3]
    • swap(1, 2) -> permute([1, 3, 2], 2, result)
      • 基准情况,添加 [1, 3, 2]
  3. swap(0, 1) -> permute([2, 1, 3], 1, result)
    • swap(1, 1) -> permute([2, 1, 3], 2, result)
      • 基准情况,添加 [2, 1, 3]
    • swap(1, 2) -> permute([2, 3, 1], 2, result)
      • 基准情况,添加 [2, 3, 1]
  4. swap(0, 2) -> permute([3, 2, 1], 1, result)
    • swap(1, 1) -> permute([3, 2, 1], 2, result)
      • 基准情况,添加 [3, 2, 1]
    • swap(1, 2) -> permute([3, 1, 2], 2, result)
      • 基准情况,添加 [3, 1, 2]

最终结果为所有排列:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]

通过这些示例,你可以看到递归在解决不同类型问题时的广泛应用。关键在于理解递归的三个部分,并通过模拟、调试和练习来逐步掌握递归的思维方式。

标签:return,递归,示例,factorial,result,深度,permute
From: https://blog.csdn.net/m0_49013185/article/details/140540149

相关文章

  • 计算机毕业设计Python+Tensorflow小说推荐系统 K-means聚类推荐算法 深度学习 Kears
    2、基于物品协同过滤推荐算法2.1、基于⽤户的协同过滤算法(UserCF)该算法利⽤⽤户之间的相似性来推荐⽤户感兴趣的信息,个⼈通过合作的机制给予信息相当程度的回应(如评分)并记录下来以达到过滤的⽬的进⽽帮助别⼈筛选信息,回应不⼀定局限于特别感兴趣的,特别不感兴趣信息的纪录也相......
  • 计算机毕业设计PySpark+Django高考志愿填报推荐系统 高考预测 高考大数据分析 Hadoop
    摘要本文旨在设计与实现一个基于Spark的高考志愿填报推荐系统,旨在帮助高考生根据自身成绩和兴趣,精准推荐合适的大学和专业。系统采用大数据处理框架Spark,结合机器学习算法,实现了对高考数据的深度挖掘和分析,为考生提供科学、有效的志愿填报建议。系统捕捉考生个人特征、......
  • 深度学习中的正则化技术 - Dropout篇
    序言在深度学习的浩瀚领域中,模型过拟合一直是研究者们面临的挑战之一。当模型在训练集上表现得近乎完美,却难以在未见过的数据(测试集)上保持同样优异的性能时,过拟合现象便悄然发生。为了有效缓解这一问题,Dropout......
  • 深度解析 Vue 3 响应式数据
    Vue3引入了全新的响应式系统,使得数据管理更为灵活和高效。本文将详细解析Vue3响应式数据的原理和使用方法,包括reactive、ref、computed、watch等核心概念,并展示如何在实际项目中应用它们。1.响应式数据的核心概念Vue3的响应式系统基于Proxy对象,通过代理数据对象来实......
  • 代码随想录算法训练营Day13 | 二叉树理论基础 二叉树的递归遍历 前序、中序、后序遍历
    一、二叉树理论基础1. 二叉树种类①满二叉树:顾名思义就是结点都满的二叉树。定义:如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。     深度为k,结点数为2^k-1的二叉树②完全二叉树:最后一层可以不满,但最后一层从左......
  • TG群导航机器人:深度检索技术的创新应用
    关键词TG群导航机器人,深度检索,信息检索,智能助手1.引言TG群导航机器人是一种运行在TG平台上的智能助手,能够根据用户的需求,自动检索并推送相关信息。通过深度检索技术的应用,机器人能够提供更加精准和个性化的信息服务。在信息泛滥的今天,精准的信息检索变得尤为重要。TG群导......
  • 吴恩达深度学习课程笔记Lesson03
    第三周:浅层神经网络(Shallowneuralnetworks)文章目录第三周:浅层神经网络(Shallowneuralnetworks)3.1神经网络概述(NeuralNetworkOverview)3.2神经网络的表示(NeuralNetworkRepresentation)3.3计算一个神经网络的输出(ComputingaNeuralNetwork'soutput)3.4多样......
  • PHP高性能递归函数
    一个递归方法functionorganizeRecords($regions){$organizedRegions=[];foreach($regionsas$region){$organizedRegions[$region['id']]=$region;$organizedRegions[$region['id']]['chi......
  • 深度学习框架入门
    #一句话说明白深度学习框架有什么用:利用编程语言来实现复杂的网络架构。不同的开发框架类似不同的语言。常见主流框架介绍 TensorFlow主要用于构建和训练深度学习模型。其强大的可视化工具(如TensorBoard)和对多种硬件的支持,使其在企业级和研究级应用中广泛使用。然而,Ten......
  • 从前序与中序遍历序列构造二叉树-递归
    题目描述:个人题解:        只要我们在中序遍历中定位到根节点,那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的,因此我们就可以对应到前序遍历的结果中,对上述形式中的所有左右括号进行定位。这样的话,我们就......