第7章函数与指针7.1 1递归函数7.2函数重载7.3指针和函数7.4带参数的main()函数7.5内联函数7.6无参函数7.7void和const类型的指针
0 第7章 函数与指针 • 7.1 递归函数 • 7.2 函数重载 • 7.3 指针和函数 • 7.4 带参数的main()函数 • 7.5 内联函数 • 7.6 无参函数 • 7.7 void和const类型的指针
本章目标掌握递归函数掌握函数重载2.+美（>3、理解指针和函数的几种关系
1 本章目标 ➢ 1、掌握递归函数 ➢ 2、掌握函数重载 ➢ 3、理解指针和函数的几种关系
7.1递归函数C++中，允许函数进行递归调用。递归调用：允许一个函数直接或间接地调用自身。若一个函数体内直接包含了调用该函数本身的语句，则称为一直接递归调用，该函数是直接递归函数。一若一个函数体内间接包含对自己的调用，则称为一一间接递归调用，该函数是间接递归函数
2 7.1 递归函数 • C++中，允许函数进行递归调用。 • 递归调用：允许一个函数直接或间接地调用自身。 • 若一个函数体内直接包含了调用该函数本身的语句，则 称为——直接递归调用，该函数是直接递归函数。 • 若一个函数体内间接包含对自己的调用，则称为——间 接递归调用，该函数是间接递归函数
7.1递归函数递归算法一个直接或间接地调用自身的算法称为递归算法。使用递归函数的优点：程序方便简洁，可读性好。编写递归函数的两要素：(1)递归定义的公式(2）递归终止的条件
3 7.1 递归函数 • 递归算法 一个直接或间接地调用自身的算法称为递归算法。 • 使用递归函数的优点： 程序方便简洁，可读性好。 • 编写递归函数的两要素： • (1)递归定义的公式 • (2)递归终止的条件
7.1递归函数例7-1：采用递归算法求n！算法：由阶乘的概念可以写出其递归的定义0! = 1n! = n * (n-1)!
4 7.1 递归函数 例7-1：采用递归算法求n! 算法：由阶乘的概念可以写出其递归的定义 0! = 1 n! = n * (n-1)!
7.1递归函数1/例7-1：采用递归算法求n！#includeusingnamespacestd:1/函数fac（）：求阶乘的递归函数int fac(intn)if(n<0)11不能求负数的阶乘return -1;1/的阶乘为elseif(n==0)returnelsereturnn*fac(n-1）；1/nt为（n-1)乘以n
5 7.1 递归函数
7.1递归函数例7-1：采用递归算法求n！分析：用递归函数fac()计算5!时的执行过程如图7-1所示。fac(5)fac (4)fac(3)main(函数中调用调用调用调用fac (5)5*fac(4)4*fac(3)3*fac(2)返回6输出120返回120返回24fac (0)fac(1)fac(2)调用调用fac (0)=11*fac (0)2*fac(1)返回1返回1返回2图7-1递归函数的调用顺序
6 7.1 递归函数 例7-1：采用递归算法求n! 分析：用递归函数fac( )计算5!时的执行过程如图7-1所示。 图7-1 递归函数的调用顺序 调用 fac(5) 输出120 main()函数中 调用 5*fac(4) 返回120 fac(5) 调用 4*fac(3) 返回24 fac(4) 调用 3*fac(2) 返回6 fac(3) 调用 2*fac(1) 返回2 fac(2) 调用 1*fac(0) 返回1 fac(1) fac(0)=1 返回1 fac(0)
7.1递归函数注意：使用递归函数时，要特别注意不要造成死循环。一个问题要能够转换为递归来处理，必须满足以下条件：（1）必须包含一种或多种非递归的基本形式。(2）一般形式必须能最终转换到基本形式。(3)由基本形式来结束递归。注意：递归调用在堆栈中临时占据的存储区域是较多的，在实际运行时，递归调用的时间效率较差
7 7.1 递归函数 • 注意： 使用递归函数时，要特别注意不要造成死循环。 • 一个问题要能够转换为递归来处理，必须满足以下条件： • (1)必须包含一种或多种非递归的基本形式。 • (2)一般形式必须能最终转换到基本形式。 • (3)由基本形式来结束递归。 • 注意：递归调用在堆栈中临时占据的存储区域是较多的，在实 际运行时，递归调用的时间效率较差
7.1递归函数经典递归问题：Ackerman函数Fibonacci数列八皇后问题梵塔问题
8 7.1 递归函数 • 经典递归问题： • Ackerman函数 • Fibonacci数列 • 八皇后问题 • 梵塔问题
7.1递归函数例7-2：梵塔（hanoi塔）问题根据古印度神话，在贝拿勒斯的圣庙里安放着一个铜板，板上插有3根一尺长的宝石针。印度教的主神梵天在创造世界的时候，在其中的一根针上摆了由小到大共64片中间有孔的金片。无论白天和黑夜，都有一位僧侣负责移动这些金片，规则是一次只能将一片金片移到另一根针上，并且在任何时候以及任一根针上，小片永远在大片的上面。当所有的64片金片都由最初的那根针移到另一根针上时，这世界就将在一片霹雳中消失
9 7.1 递归函数 例7-2：梵塔(hanoi塔)问题 根据古印度神话，在贝拿勒斯的圣庙里安放着一个铜 板，板上插有3根一尺长的宝石针。印度教的主神梵天在 创造世界的时候，在其中的一根针上摆了由小到大共64 片中间有孔的金片。无论白天和黑夜，都有一位僧侣负 责移动这些金片，规则是一次只能将一片金片移到另一 根针上，并且在任何时候以及任一根针上，小片永远在 大片的上面。当所有的64片金片都由最初的那根针移到 另一根针上时，这世界就将在一片霹雳中消失