数据结构和算法—递归机制剖析|学习笔记

简介: 快速学习数据结构和算法—递归机制剖析

开发者学堂课程【Go 语言核心编程 - 数据结构和算法:数据结构和算法—递归机制剖析】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9861


数据结构和算法—递归机制剖析


内容介绍

一、引出递归

二、递归是什么

三、分析过程

四、总结

 

一、引出递归

前面内容的递归中没有涉及回溯问题,现在来看一个相对比较复杂的,涉及递归回溯的问题。有一个实际应用场景

image.png

小老鼠从左上角走到右下角,但是存在问题:中间的方格中可能存在障碍无法通过,并且小老鼠行走的路径有很多条选择,我们不知道小老鼠最终能到个位置,或者说并不知道条路最短,这就需要用递归来解决。

用这个应用场景引出递归,接下来先来看一下递归的应用概论。

递归是什么?

简单的讲,递归就是函数或者一个方法,自己调用自己,每次调用时传入不同的变量,归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

 

二、递归快速入门

列举两个小案例,帮助大家理解递归,递归在讲函数时已经讲过,这里再给大家回顾一下递归调用机制

打印问题

阶乘问题

以打印数字为例

package main

import(

fmt

)

func test(n int) {

if n > 2 {

n--

test(n)

}

fmt.Println(n=,n)

}

func main() {

n :=4

test(n)  

}

代码中有一个函数 test,可以接受一个n值,如果这个n值大于二,n--再调用自己,就是递归调用。

调用完后继续进行循环最终输出结果。

 

三、分析过程

分析过程:

 image.png

画一个框可以理解它是一个内存,内存中有一部分是栈。栈中有一部分为主栈,栈中有一个变量为 n,n=4。

当我们的程序从主函数 func main(){n:=4  test(n)}开始执行时,执行 n=4,然后进行调用这时会去开辟一个新的空间,我们可以理解成一个新的栈,但是它仍然是在大的栈里面。

在调用 test 的时候,会先对原值做一个保存,栈创建了一个新的空间,调用的函数的新的栈压在空间上面。

继续执行 func test(n int){}的代码,而此处的 n 也存在栈的一个空间中, n=4。但是两个空间的 n 不冲突,现在继续判断 n 是否>2,执行到 n--,注意 n--是对上方栈里的 n--,4减成了3。

之后又调用 test,又开辟了一个新栈,该新栈中也有一个 n,n=3。再判断是否>2又执行 n--,该 n 变成2。又调用 test,这时 test 又根据函数调用的规则又开辟一个新的栈,n=2,判断n是否>2,执行代码 fmt.Println(n=,n),输出 n 等于2。

从栈顶开始依次往下不断执行代码。从 test 进去,往下执行,不断输出栈,输出完之后又继续往下面走,相当于从 test 进入,不断执行下面,当它把 n 等于3输出之后,到了主栈,主栈又返回。结果就是输出n=2 n=2 n=3

运行代码:

分析过程结束后,来运行代码查看结果,运行结果为 n=2 n=2 n=3。

再来做一个改变:

在代码 if 块增加 else,即

if n > 2 {

n--

test(n)

}else{

fmt.Println(n=,n)

}

先来分析:

主栈位置不变,栈顶 n=2,所以执行 else 语句,输出 n 等于2,一旦输出后栈顶往下,对第二个栈,是从 if 中的 test 进入,所以不会输出。到第三个栈也是从 if 中的 test 进入,也不会输出。

最后只输出 n=2

所以数据是独立的,代码也要根据实际情况执行,加了 else 输出的结果只有一个,栈顶输出2。

再尝试执行代码 ,结果显示 n=2

 

四、总结

以上内容回顾了递归调用的机制,

总结笔记:

首先提出一个递归应用场景,《迷宫的问题》,由迷宫问题引出了递推概论即方法自己调用自己。

例如显示目录数或者排序或者查找都是方法自己调用自己,因此引出递归。借助原先讲的案例打印问题进行回顾。

此外还有阶乘问题,快速入门的示意图。

快速入门的示意图如下

image.png

相关文章
|
5月前
|
存储 监控 算法
基于 C++ 哈希表算法实现局域网监控电脑屏幕的数据加速机制研究
企业网络安全与办公管理需求日益复杂的学术语境下,局域网监控电脑屏幕作为保障信息安全、规范员工操作的重要手段,已然成为网络安全领域的关键研究对象。其作用类似网络空间中的 “电子眼”,实时捕获每台电脑屏幕上的操作动态。然而,面对海量监控数据,实现高效数据存储与快速检索,已成为提升监控系统性能的核心挑战。本文聚焦于 C++ 语言中的哈希表算法,深入探究其如何成为局域网监控电脑屏幕数据处理的 “加速引擎”,并通过详尽的代码示例,展现其强大功能与应用价值。
109 2
|
3月前
|
存储 监控 安全
企业上网监控系统中红黑树数据结构的 Python 算法实现与应用研究
企业上网监控系统需高效处理海量数据,传统数据结构存在性能瓶颈。红黑树通过自平衡机制,确保查找、插入、删除操作的时间复杂度稳定在 O(log n),适用于网络记录存储、设备信息维护及安全事件排序等场景。本文分析红黑树的理论基础、应用场景及 Python 实现,并探讨其在企业监控系统中的实践价值,提升系统性能与稳定性。
73 1
|
3月前
|
存储 监控 算法
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
83 0
|
7月前
|
存储 算法 Java
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
189 10
 算法系列之数据结构-二叉树
|
6月前
|
存储 Java 编译器
Java 中 .length 的使用方法:深入理解 Java 数据结构中的长度获取机制
本文深入解析了 Java 中 `.length` 的使用方法及其在不同数据结构中的应用。对于数组,通过 `.length` 属性获取元素数量;字符串则使用 `.length()` 方法计算字符数;集合类如 `ArrayList` 采用 `.size()` 方法统计元素个数。此外,基本数据类型和包装类不支持长度属性。掌握这些区别,有助于开发者避免常见错误,提升代码质量。
470 1
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
158 3
 算法系列之数据结构-Huffman树
|
7月前
|
算法 Java
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
196 22
|
6月前
|
存储 算法 物联网
解析局域网内控制电脑机制:基于 Go 语言链表算法的隐秘通信技术探究
数字化办公与物联网蓬勃发展的时代背景下,局域网内计算机控制已成为提升工作效率、达成设备协同管理的重要途径。无论是企业远程办公时的设备统一调度,还是智能家居系统中多设备间的联动控制,高效的数据传输与管理机制均构成实现局域网内计算机控制功能的核心要素。本文将深入探究 Go 语言中的链表数据结构,剖析其在局域网内计算机控制过程中,如何达成数据的有序存储与高效传输,并通过完整的 Go 语言代码示例展示其应用流程。
105 0
|
7月前
|
存储 监控 算法
基于 PHP 二叉搜索树算法的内网行为管理机制探究
在当今数字化网络环境中,内网行为管理对于企业网络安全及高效运营具有至关重要的意义。它涵盖对企业内部网络中各类行为的监测、分析与管控。在内网行为管理技术体系里,算法与数据结构扮演着核心角色。本文将深入探究 PHP 语言中的二叉搜索树算法于内网行为管理中的应用。
70 4
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
223 59

热门文章

最新文章