《递归与搜索上》课件.pptx

《《递归与搜索上》课件.pptx》由会员分享，可在线阅读，更多相关《《递归与搜索上》课件.pptx（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、递归与搜索上ppt课件递归概述递归算法递归与栈搜索算法递归与搜索的应用01递归概述递归是指在函数或算法中直接或间接调用自身的一种方法。它通过将问题分解为更小的子问题来解决，子问题的求解过程与原问题相同。递归的基本思想是将复杂问题转化为简单问题来解决。递归的定义递归的基本思想是将问题分解为更小的子问题，直到子问题可以简单地直接求解。然后通过子问题的解来构建原问题的解。递归的基本思想包括两个主要步骤：分解和组合。分解是将原问题分解为更小的子问题，组合是将子问题的解组合起来得到原问题的解。01020304递归的基本思想直接递归是指函数或算法直接调用自身来解决问题。间接递归是指函数或算法通过调用其他函

2、数或算法间接地调用自身来解决问题。根据递归的性质，可以将递归分为两类：直接递归和间接递归。递归的分类02递归算法阶乘递归算法01阶乘递归算法是一种常见的递归算法，用于计算一个正整数的阶乘。阶乘是一个数与比它小的所有正整数的乘积。例如，5的阶乘（记作5!）是5*4*3*2*1=120。递归步骤02阶乘递归算法的递归步骤包括将问题分解为更小的子问题（例如，计算n的阶乘可以分解为计算(n-1)的阶乘），然后使用这些子问题的解来解决原始问题。时间复杂度03阶乘递归算法的时间复杂度是指数级的，因为每个问题都可能导致大量的子问题。因此，对于较大的输入，阶乘递归算法可能会变得非常慢。阶乘递归算法递归步骤斐波

3、那契数列递归算法的递归步骤包括使用前两个数字来计算下一个数字。例如，要计算第n个斐波那契数，可以使用第n-1和第n-2个斐波那契数。斐波那契数列斐波那契数列是一个无穷整数序列，其中每个数字是前两个数字的和。序列的前几个数字是0、1、1、2、3、5、8、13等。时间复杂度斐波那契数列递归算法的时间复杂度也是指数级的，因为对于较大的输入，该算法会涉及大量的重复计算。斐波那契数列递归算法递归步骤汉诺塔递归算法的递归步骤包括将问题分解为更小的子问题（例如，将一组盘子从一个柱子移动到中间柱子），然后使用这些子问题的解来解决原始问题。时间复杂度汉诺塔问题的最坏情况时间复杂度是O(2n)，其中n是盘子的数量

4、。这是因为对于每个盘子，都存在两个移动的选择，并且这些选择是相互排斥的。汉诺塔递归算法03递归与栈栈是一种后进先出（LIFO）的数据结构，用于存储数据的列表。栈中的数据只能从一端（称为栈顶）添加或移除。栈具有两个主要操作：压栈（push）和弹栈（pop）。栈的基本概念 递归与栈的关系递归函数在执行过程中会使用栈来保存函数调用时的状态。当函数被调用时，它的参数和局部变量会被压入栈中，以便在函数返回时恢复执行。当函数返回时，其局部变量和参数从栈中弹出，恢复到调用前的状态。递归函数在执行时，首先将当前函数调用信息（如参数、局部变量等）压入栈中。然后进入递归调用的执行过程，直到遇到返回语句或递归终止条

5、件。在返回时，从栈中弹出之前保存的函数调用信息，恢复到调用前的状态，并继续执行后续代码。递归调用的执行过程04搜索算法从列表的第一个元素开始，逐个检查每个元素，直到找到目标元素或遍历完整个列表。线性搜索算法时间复杂度适用场景O(n)，其中n是列表的长度。当列表较小且未排序时，线性搜索算法是简单且有效的。030201线性搜索算法在已排序的列表中，每次比较中间元素与目标元素，根据比较结果决定搜索区间，不断缩小搜索范围，直到找到目标元素或搜索区间为空。二分搜索算法O(log n)，其中n是列表的长度。时间复杂度当列表较大且已排序时，二分搜索算法具有较高的效率。适用场景二分搜索算法深度优先搜索算法按照

6、深度优先的顺序遍历图或树结构，尽可能深地搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。时间复杂度O(n)，其中n是图或树的节点数。适用场景用于遍历或搜索树或图结构，适用于具有层次结构的数据集。深度优先搜索算法05递归与搜索的应用使用递归进行分区和比较，通过搜索分区内的元素来达到排序的目的。快速排序递归地将数组分解为更小的子数组，然后合并已排序的子数组来得到最终的排序结果。归并排序通过构建最大堆或最小堆，然后依次取出堆顶元素，再调整堆，实现排序。堆排序排序算法中的递归与搜索采用分治策略，递归地将数组分解为更小的子数组，然后合并已排序的子数组来得到最终的排序结果。合并排序在有序数组中，通过不断将搜索范围缩小一半来找到目标元素。二分查找利用分治策略，将矩阵乘法转化为多个小规模的矩阵乘法问题，然后递归地求解这些小问题。矩阵乘法分治算法中的递归与搜索树图哈希表数据结构中的递归与搜索树是一种常见的数据结构，可以通过递归的方式遍历树的节点，如前序遍历、中序遍历和后序遍历。图是一种复杂的数据结构，可以通过深度优先搜索（DFS）或广度优先搜索（BFS）进行遍历。DFS使用递归实现，BFS则使用队列实现。哈希表是一种基于哈希函数的数据结构，可以通过哈希函数计算出元素在哈希表中的位置，然后进行搜索和插入操作。感谢观看THANKS