递归函数ppt

《C语言递归算法》PPT 课件
C语言递归算法是一种强大的编程技巧，通过函数自身调用实现问题的解决。 本课件将介绍递归算法的概念、实现方式、应用场景、优缺点以及与循环的 区别，同时还会通过案例演示帮助理解。
什么是递归算法？
基本概念
递归是指函数直接或间接地调用自身的过程。
递归特点
递归算法需要有基准条件和递推关系，用于结 束递归和推进递归过程。
递归算法的实现方式
递归函数
通过函数自身调用实现递归，需要定义递归函数和 递归终止条件。
递归流程图
通过流程图展示递归算法的执行过程，帮助理解递 归逻辑。
递归算法的应用场景
1 数学计算
递归算法可以用于解决数学问题，如斐波那契数列、阶乘等。
2 数据结构
递归算法在树、图等数据结构的遍历和搜索中有广泛应用。
递归算法的优点和缺点
优点
• 简化问题复杂度 • 代码结构清晰
缺点
• 执行效率较低 • 内存占用较高
递归算法与循环的区别
1
循环
2
迭代操作
3
递归
函数自身调用
区别
递归更直观，但消耗资源较多；循环更 高效，但代码可读性差。
递归算法的注意事项
1 递归终止条件
保证递归过程能够结束，否则可能导致死循 环。
2 堆栈溢出
过深的递归调用可能导致堆栈溢出，需要注 意递归深度。
递归算法的案例演示
斐波那契数列
通过递归实现斐波那契数列的计算。
二叉树遍历
通过递归遍历二叉树的各种方式。

递归的定义
若一个对象部分地包含它自己, 或用它自己给自 己定义, 则称这个对象是递归的；若一个过程直接地 或间接地调用自己, 则称这个过程是递归的过程。
递归的定义
直接递归 fun_a() {… fun_a() … }
间接递归 fun_a() {… fun_b() …}
fun_b() {… fun_a() …}
c1, c2,……，cm是若干个可以直接（用非递归方法）解决的问题， g是一个非递归函数，反映了递归问题的结构。
递归模型
例如，阶乘函数 递归出口
1,
当n0时
n! n(n1)!, 当n1时
递归体
ห้องสมุดไป่ตู้
递归的执行过程
实际上，递归是把一个不能或不好直接求解的 “大问题”转化为一个或几个“小问题”来解决，再 把这些“小问题”进一步分解成更小的“小问题”来 解决，如此分解，直至每一个“小问题”都可以直接 解决（此时分解到递归出口）。
递归调用执行过程：
... ...
main() x=17
bn=bSearch(a,x,0,7)
...
bn=bSearch(a,x,0,7)
mid=3 bn=bSearch(a,x,4,7)
...
4
...
return(bn=bSearch(a,x,4,7))
mid=5
bn=bSearch(a,x,4,4)
6.1 递归的概念
若一个算法直接地或间接地调用自己本身，则称 这个算法是递归算法。
1.问题的定义是递归的
例如：阶乘函数的定义
1
当n=0时
n=
n*(n-1) 当n>0时
2. 问题的解法存在自调用 例如：折半查找算法

题的运行效率较低。所以一般不提倡用递归算法 设计程序
递归法的归纳2：
递归算法所体现的“重复”一般有三个要求： 一是每次调用在规模上都有所缩小(通常是减半)； 二是相邻两次重复之间有紧密的联系，前一次要为
后一次做准备(通常前一次的输出就作为后一次的 输入)； 三是在问题的规模极小时必须用直接给出解答而不 再进行递归调用，因而每次递归调用都是有条件 的(以规模未达到直接解答的大小为条件)，无条 件递归调用将会成为死循环而不能正常结束。
• 注意：必须要有一个结束递归的条件，不 得无限递归。
分析步骤：
• 1.决定问题规模的参数。 • 2.问题的边界条件及边界值。 • 3.解决问题的通式。
例:计算一个数的阶乘
• 1!=1 • 2!=1*2 • 3!=1*2*3 • 4!=1*2*3*4 • 5!=1*2*3*4*5 • ……. • n!=1*2*3*4*5*….*n
函数是为了实现某种功能而编写的一段相对独立 的程序。
• 标准函数
Abs( ) 、len( )、mid( )、chr( )、asc( )……
• 自定义函数
自定义函数是指我们自己编写的函数。
自定义函数:
• 在VB中，自定义函数形式如下： • [Public|Private] Function <函数名称> ([参数列表]) [As
f(1)=1 f(2)=f(1)*2 f(3)=f(2)*3 f(4)=f(3)*4 f(5)=f(4)*5 …….. f(n)=f(n-1)*n
递归函数求5！
• Public Function s(n As Integer) As Long
• If n = 1 Then
• s =1
• Else

04 可变参数：使用*args或**kwargs来接收任意数量 的参数，可以方便地处理参数个数可变的情况
参数默认值
01
什么是参数默认值：在函数定 义时，为参数指定一个默认值， 当调用函数时，如果没有提供 该参数的值，则使用默认值。
02
默认值的作用：简化函数调 用，提高代码可读性和可维 护性。
03
如何设置参数默认值：在函数 定义时，在参数名后使用等号 （=）为参数指定默认值。
谢谢
4
形参和实参的类型可以不同，但必须兼容
5
形参和实参可以传递任意类型的数据，包括数值、字符串、列表、字典等
参数传递方式
01 值传递：将实参的值传递给形参，形参的改变不影 响实参
02 引用传递：将实参的地址传递给形参，形参的改变 会影响实参
03 默认参数：在定义函数时为参数指定默认值，调用 函数时可以省略该参数
函数的嵌套
01 概念：在一个函数内部定义并 调用另一个函数
02 作用：简化代码，提高代码可 读性和可维护性
03 示例：计算阶乘的函数中嵌套 计算每个数的阶乘
04 注意事项：避免嵌套层次过深， 可能导致代码难以理解和调试
递归函数的定义
01
递归函数是一种函数，它直接或间接 02
递归函数通常用于解决可以分解为更
性
函数的作用
01
02
03
04
简化代码：将重复 代码封装成函数， 提高代码可读性和
可维护性
提高代码重用性： 将可重用的代码封 装成函数，方便在
其他地方调用
提高代码模块化： 将相关功能封装成 函数，便于模块化
编程
提高代码执行效率： 通过函数调用，减 少重复计算，提高