当前课程知识点:C语言程序设计 > 第8章 函数 > 8.6 函数的嵌套和递归调用 > 函数的嵌套和递归调用
同学们
大家好
今天我们来讲
函数的嵌套与递归调用
C语言规定
函数不可嵌套定义
但可嵌套调用 例如
这个例子中
总共有4个函数
main函数
自定义函数dif函数
max函数
min函数
main函数中请求用户输入3个数到a b c中
然后调用dif函数求3个数的最大值和最小值之差
然后输出
而dif函数由调用了自定义函数max和min函数
分别求3个数的最大值和最小值
这就是一个典型的函数的嵌套调用
下面来看函数的递归调用
函数的递归调用
指的是
函数直接或间接的调用自身
分为直接递归和间接递归
例如
这程序中
f函数在其中某个位置调用了f函数自己
执行了z=f(y)
这就是直接递归
即
函数中某个位置又直接调用函数自身
函数递归
大多数属于这种情况
间接递归
比如下面这个例子
函数f1调用了函数f2
而f2又在某个位置调用了f1
这叫做间接递归
实际当中这种情况比较少
下面以具体的例子来说明
例如
这个程序中的print函数
参数为w
if语句中通过print(w-1)语句来直接调用了自己
然后使用for循环循环执行了w次
输出w
这件事
而main函数中只有一条语句
print(3)
即以w=3位参数
调用print函数
那么
程序的运行结果我们可以看到
是
第一行出现了1个1
第二行出现了两个2
也就是说第n行出现了n个n
下面分析它的执行情况
它的执行情况
可以用这张图来描述
程序从main函数中开始
只有一行语句
即以w=3为参数调用print函数
而根据print函数执行的代码
当w不等于0时
便执行print(w-1)
然后输出w个w
因此
print(3)做的事情是
先调用print(2)
然后输出三个3
但注意
输出三个3
这个操作要等print2
调用结束后才执行
那么print(2)又做了什么事情呢
还是根据前面的规则
print(2)先调用print(1)
然后输出两个2
因此
可以将print(2)替换为
调用print(1)
然后输出两个2
即屏幕上梅红色下划线文字
但仍然要注意
输出两个2
这个操作
要在print(1)调用结束后才执行
接下来只需要将print(1)做类似的替换即可
即
将print(1)替换为
调用print(0)
然后输出1个1
这样
print(2)
就等价于了
先调用print(0)
然后输出1个1
再然后输出两个 2
那么最后
再将print(0)做相应替换即可
print(0)做了什么呢
根据print函数的代码
当参数w=0时
将不执行任何代码
所以print(0)什么事情都没有做
即直接返回
所以
将print(0)替换为
什么事情都不做直接返回
此时
print(0)函数调用的任务就已结束
那么print(1)的后半部分
即输出1个1
便被执行
所以
结果最先输出了1个1
输出完毕后
print1的函数调用任务也结束
可以执行print2
函数调用的后半部分
即
输出两个2
所以
屏幕然后输出了
两个2
至此
print2的函数调用任务也结束了
可以执行print3
函数调用的后半部分
即输出三个3
所以最后输出了
三个3
至此print3
函数调用结束
这就是函数递归的执行过程
需要注意的是
函数的递归
必须要有递归结束条件
例如
这个例子中
当w=0时
递归结束
w=0就是递归结束条件
如果不设置递归结束条件
那个函数递归
将成为一个死循环
我们要避免这种情况的发生
下面再举一个例子
利用递归
求n的阶乘
以前我们讲过可以用循环来求n的阶乘
那么今天
我们使用函数的递归来解决这个问题
在这里
我们要利用阶乘的特性
即当n=1时
n的阶乘等于1
而当n>1时
n的阶乘等于n乘以n-1的阶乘
若我们将n的阶乘定义为函数f(n)
那么
当n>1时
f(n)就等于n乘以f(n-1)
这就是递归表达式
而递归什么时候结束呢
当n=1时
f(n)等于1
这是确定的
这就是递归结束的条件
下面给出代码
在这个程序中
定义了f函数
用于求n的阶乘
当n为1时
直接返回了1
否则
当n不等于1时
返回了n乘以f(n-1)
及n乘以n-1的阶乘
这里的n=1
便是递归结束条件
而n*fn-1
便是递归调用表达式
main 函数
调用f函数计算并输出了5的阶乘
即f5
得到了120的运行结果
那么f(5)这个函数调用的执行过程
也比较简单
按照f函数
f(5)应该返回5*f(4) 而f(4)又返回4*f(3)
所以f(5)就等于5*4*f(3)
而f(3)又返回3*f(2)
所以
f(5)又等于5*4*3*f(2)
而f(2)又返回2*f(1)
所以
f(5)又等于5*4*3*2*f(1)
而f(1) 返回1
因此
得到f(5)等于5*4*3*2*1=120
类似还可用递归解决的典型问题
例如汉诺塔问题
大家可以自行学习
好
函数的递归我们就讲到这里
我们下次再见
-计算思维与计算机
--计算思维与计算机
--计算思维与计算机
--计算思维和计算机
-2.1 程序设计语言的发展及其特点和应用
--程序设计语言的特点及发展
- 2.2 C语言程序的基本结构及编制C语言程序的基本步骤
--C语言程序的结构和编制步骤
-3.1 C语言的数据类型
--C语言的数据类型
--C语言的数据类型
-3.2 常量
--常量
--常量
-3.3 什么是变量
--什么是变量
--什么是变量
-3.4 如何进行算术运算
--如何进行算术运算
--如何进行算术运算
-3.5 赋值运算符和逗号运算符
--赋值运算符和逗号运算符
-3.6 数据类型转换
--数据类型转换
--数据类型转换
-4.1 格式化输出printf
--格式化输出
-4.2 格式化输入scanf及字符数据的非格式化输入输出
--格式化输入
-5.1 关系运算符和关系表达式
--关系运算符和关系表达式
-5.2 逻辑运算符和逻辑表达式
--逻辑运算符和逻辑表达式
-5.3 条件运算符和条件表达式
--条件运算符和条件表达式
-5.4 if语句
--if语句
--if语句
-5.5 switch语句
--switch语句
--switch语句
-6.1 while语句
--while语句
--while语句
--do-while语句
-6.2 for语句
--for语句
--for语句
-6.3 循环的嵌套
--循环的嵌套
--循环的嵌套
-6.4 break语句和continue语句
--break和continue语句
-7.1 一维数组的定义和引用
--一维数组的定义和引用
-7.2 一维数组的赋值
--一维数组的赋值
--一维数组的赋值
-7.3 二维数组的定义和引用
--二维数组的定义和引用
-7.4 二维数组的赋值
--二维数组的赋值
--二维数组的赋值
-7.5 字符串的本质
--字符串的本质
--字符串的本质
-7.6 字符串操作的常用函数
--字符串常用函数
-7.7 字符串数组
--字符串数组
--字符串数组
-8.1 函数概述
--函数概述
--函数概述
-8.2 有参函数
--有参函数
--有参函数
-8.3 函数参数的传递方式
--函数参数的传递方式
-8.4 变量的作用域和生存期
--变量的作用域和生存期
-8.5 变量的存储类型
--变量的存储类型
--变量的存储类型
-8.6 函数的嵌套和递归调用
--函数的嵌套和递归调用
-8.7 函数的作用域与封装
--函数的作用域与封装
-9.1 指针变量的概念(上)
--指针变量的概念(上)
-9.2 指针变量的概念(下)
--指针变量的概念(下)
-9.3 指向一维数组的指针变量
--指向一维数组的指针变量
-9.4 指向二维数组的指针变量(上)
--指向二维数组的指针变量(上)
-9.5 指向二维数组的指针变量(下)
--指向二维数组的指针变量(下)
-9.6 动态内存分配
--动态内存分配
--动态内存分配
-10.1 编译预处理
--编译预处理
-11.1 用户自己建立数据类型
--用户自己建立数据类型
-11.2 定义结构体类型变量
--定义结构体类型变量
-11.3 结构体变量的引用与初始化
-11.4 结构体数组
--结构体数组
--结构体数组
-11.5 指向结构体类型数据的指针
--指向结构体类型数据的指针
-12.1 文件的基本概念和文件指针
--文件的基本概念和文件指针
-12,2 文件的打开和关闭
--文件的打开和关闭
--文件的打开和关闭
-12.3 文本文件读写
--文本文件读写
--文本文件读写
-12.4 二进制文件读写
--二进制文件读写
--二进制文件读写