当前课程知识点:C语言程序设计(下) > 第二周:函数(二) > 函数递归调用 > 6.5.2 递归定义和调用过程
刚才咱们说到了
从前有个山 山里有个庙
庙里有个和尚讲故事
这种古老的故事
函数的递归调用
正像是这个故事这样
你中有我 我中有你
下面我们就从
一个具体的问题开始介绍
函数的递归
如果
我们要求一个非负整数
n的阶乘
例如n为4
那么
这个问题就
可以从数学的角度来分析
4的阶乘
应该等于
把它写成一种算法
那就是
4的阶乘
等于4乘上3的阶乘
3的阶乘
又等于3乘2的阶乘
所以
这个算法
应该包含了解决如下两个问题
第一
如果
n的值为1或为0
这时候
阶乘的值就为1
如果n大于1
那么
n的阶乘就应该是
n乘上n-1的阶乘
把这种算法
可以描述成
这样的数学公式
那么
用我们前面学过的函数的定义
我们就来写一段功能函数
来求一个整数n的阶乘
大家看
在这
我们定义一个功能函数
函数类型为浮点型
函数名为fact
整型变量n
作为函数的形参
在这个函数体中
咱们定一个浮点变量f
就是来
获取求得的阶乘
因为是非负整数
所以
如果n小于0
我们给出一个出错的提示
如果n的值为0
或为1
把1赋给f
否则
就将n
乘上
以n-1为参数
调用这个功能函数
把乘得的结果再赋给f
函数调用结束
返回f的值
从这个函数不难理解
求阶乘这个算法的实现
这段函数还提醒我们
在这个函数的定义中
出现了函数的调用
也就是说
一个函数自身调用了自己
这个就是递归
那么现在我们来看
递归的基本概念
递归调用就是一个函数
直接或间接的调用了它自身
称为函数的递归调用
简称递归
递归函数的执行过程
又是什么样呢
我们下面
还是以刚才这个求阶乘的例子来看
如果咱们编写一段主函数
在主函数中
我们输入一个n的值
假如我们输入的是4
以n为形参
调用功能函数
此时
程序的流程就转到了这个
求阶乘的函数
4
作为实参
传给了
功能函数中的形参n
按照我们刚才的分析
这个程序运行的结果
就将函数返回值f
也就是4的阶乘
代回到主调函数中
赋给y
其实
编写一个求阶乘的递归函数
可以有不同的方式
就像我们刚才写的这个
我们管它叫阶乘函数1
大家看这个函数
在这个函数中
咱们定义的是浮点变量s
作为求得的阶乘
与刚才不同的是
此时的边界条件为
当n为0的时候
0的阶乘为1
那只要不为0
我们首先将
n-1为参数的函数调用结果
赋给s
然后让s再乘上当前的n
再赋给新的s
以此来求得
当n为参数的时候的阶乘
假定
我们现在以n为4为例
来看一下阶乘函数2的调用过程
是什么样的
大家看
当实参为4的时候
进入函数体内
首先判断边界条件
那么此时n不为0
程序执行
以n-1为参数
调用函数
那此时的参数为3
这时
程序的流程就转向了
递归函数的
下一次调用
也就是
以n-1 n的值为3
为参数
调用这个递归函数
在这次调用中
同样首先判断的是边界条件
此时n不为0
程序执行
将此时的n-1
也就是3-1为2
以2为参数
调用这个递归函数
函数开始下一次的调用
当n的值为2时
首先判断边界条件
那么不为0
又转向下一次
以这时候的n-1
也就是以1为参数
再一次调用
递归函数
n为1
同样要判断是否符合边界条件
刚才我们说了
这一个函数中边界条件是为0
所以
此时仍然执行的是
以当前的n-1为参数
又开始下一次的调用
那这时候
再次调用这个递归函数
n的值为0
很显然满足了边界条件
将1赋给此时的s
程序转向最后一个返回语句
返回到哪呢
显然
主调函数调用被调函数之后
返回到主调函数中
调用被调函数的
位置
向后继续执行
因此我们现在看到
当n为0调用完阶乘函数之后
程序的流程返回到
当n为1的时候
继续刚才的语句之后的语句执行
这时
在这一个函数中
n的值为1
乘上返回值1
得到了
在n为1为参数时的s
那么同理
当n为1
函数调用结束
函数的返回值将返回到
上一层调用
也就是n为2为参数调用时
那个位置
继续前面的语句
得到了
n为2时函数调用的返回值
依此类推
n为2函数调用结束
返回到它的上一层
也就是
n为3
在调用递归函数时的位置
继续后续语句的执行
所以此时
将返回值2乘上
在这个函数内的参数
n为3
得到的是s的值为6
那么执行这条返回语句
将
返回值6
代到
上一层调用
也就是n为4时
调用这个递归函数
将返回值6乘上当前的n
也就是4
得到的最后的4的阶乘为
24
由此看来
函数的递归就是这样
那么我们对递归作以下说明
比如我们看右侧这图
我们一开始用n为4
来调用函数
在n为4调用函数过程中
有用到了以3为参数
调用功能函数
那么这些同名的变量
n为4 n为3
n为2等等
每次调用
它们占用的空间是不同的
显而易见
就像我们刚才看到的
当n为0那一次调用结束
获得了返回值
s为1
这时返回到上一层
那么同时
程序取得
当时进入那一层时
函数中的变量和形参
所占空间中的数据
这就是
在递归调用中的
变量的存储空间的
占用的情况
和返回的情况
刚才我们说的求阶乘
是一种数值类的递归问题
这类的问题
我们还可以有一些例子
比如说
在我们学循环的时候
大家学过一个
斐波纳契数列
也就是说
求一个数列
根据我们前面的分析
我们解决这个问题的思路就是
首先这个是一个数学的问题
是一个数值类的
递归的问题
那么对于数值类递归的问题
我们首先设法
找到解决这个问题的数学公式
那么不难看出
这个序列中的第n项
等于它的前两项之和
也就是
这是第一步
第二步
这个问题怎么结束
也就是说
我们要找出递归的结束条件
很显然
当n的值为1
和n的值为2的时候
FN的值就为1
根据以上的思路
我们就可以编写
下面的这段程序了
我们定义
这一段功能函数的
函数类型为长整型
定义函数名为
fib
整型变量n为函数的形参
当n的值小于等于2
函数返回1
否则
就返回同名调用这个函数
以n-1为实参
再加上同名调用以n-2为实参
那这个就是
解决斐波那契序列中
第N项数值的递归的算法
从这可以看出
结束的条件就是
当n小于等于2的时候
返回值为1
通过以上分析
我们总结一下
编写的递归程序的要点
那么前两个例题
都是数值类的
对数值类的递归问题
可以表达成数学公式
那我们就从数学公式
推导出这个问题的递归的定义
也就是
算法之中的具体的步骤
然后确定问题的边界条件
从而找到递归的算法
和递归的结束条件
了解了递归的基本的定义
和递归程序的调用过程
我们就多做一些例题来看看
首先我们从c语言的运行环境中
来看看求阶乘
和求斐波那契数列的
第N项的应用实例
-1.1 函数定义
--内容简介
--函数是什么
--例题演示
--知识点总结
-1.1 函数定义--作业
-1.2 模块化程序设计
-1.3 函数调用、声明和返回
--函数调用的过程
--函数嵌套调用
-1.4 函数间参数传递
--形参与实参值传递
--小结
--html
-1.4 函数间参数传递--作业
-函数递归调用
--html
--html
--html
--html
--html
--html
-函数递归调用--作业
-3.1 变量存储属性
--开场
--局部变量全局变量
--存储类别小结
--html
--html
--html
--html
--html
-3.1 变量存储属性--作业
-3.2 编译预处理
--编译预处理开头
--编译预处理内容
--库函数
--函数总结
--综合例子
--html
-3.2 编译预处理--作业
-4.1 指针的定义、初始化和引用
--本周内容简介
-4.1 指针的定义、初始化和引用--作业
-4.2 指针与数组
--指针与数组
--Video
-4.2 指针与数组--作业
-5.1 指针与字符串
--本周开篇介绍
--指针与字符串
--指针与字符串小结
-5.1 指针与字符串--作业
-5.2 多维数组指针
--指针与多维数组
--html
--html
--html
--html
--html
--html
--html
--html
-5.2 多维数组指针--作业
-6.1指针与函数
--本周开篇介绍
--指针指向函数
--返回指针值的函数
--html
--html
--html
-6.1指针与函数--作业
-6.2指针与指针
--引入指针数组
--指针数组
--二级指针
--指针内容小结
--html
--html
--html
--html
-6.2指针与指针--作业
-7.1 结构的概念
--Video
--Video
--Video
--Video
--html
--html
-7.1 结构的概念--作业
-7.2 结构数组
--Video
--Video
--html
-7.2 结构数组--作业
-7.3 结构指针
--Video
--Video
--Video
--html
-7.3 结构指针--作业
-7.4 结构与函数
--Video
--html
-7.4 结构与函数--作业
-7.5 联合
--Video
--Video
--html
-7.5 联合--作业
-8.1 typedef自定义类型
--自定义类型
-8.1 typedef自定义类型--作业
-8.2 枚举类型
--枚举类型
-8.2 枚举类型--作业
-8.3 链表的概念
--为什么使用链表
--链表的定义和功能
-8.3 链表的概念--作业
-8.4 链表的基本操作
--创建链表的步骤
--创建链表的过程
--访问链表中的节点
--约瑟夫问题
--html
--html
-8.4 链表的基本操作--作业
-9.1 文件概述
--文件概念
--文件分类
-9.1 文件概述--作业
-9.2 文件型指针
--文件结构与指针
--设备文件
--html
-9.2 文件型指针--作业
-9.3 文件的打开与关闭
--文件读写方式
--文件读写操作
-9.3 文件的打开与关闭--作业
-9.4 文件的顺序读写
--字符串输入输出
--html
-9.4 文件的顺序读写--作业
-9.5 文件的随机读写
--文件随机读写
-9.5 文件的随机读写--作业
-9.6 文件检测
--文件检测
-9.6 文件检测--作业
-9.7 文件应用实例
--文件应用实例
--html
--html
-10.1 C语言知识总结
--程序调试概念
--软件测试方法
--程序跟踪调试
--C语言语法要点
--标识符及运算符
--程序设计流程
--数组、函数及指针
--结构和文件
-10.1 C语言知识总结--作业
-10.2 C语言练习
--程序设计方法
--图像合成例子
--html
-期末考试复习题
--html
-期末考试复习题答案
--html