当前课程知识点:C语言程序设计(下) > 第二周:函数(二) > 函数递归调用 > 6.5.7 递归调用例题
现在咱们就来一起做点练习
先看第一个题
比如
有五个小孩都编了号
从第一号到第五号
他们坐到一块
然后
来了个人问第五个小孩
问你多大了
他指着四号小朋友说
比他大两岁
再问四号小朋友你多大了
他说比第三个小朋友
大两岁
每个小孩都说
比他前面的小朋友大了两岁
到第一个
第一个说我10岁了
现在就让我们编程来求
如果从键盘输入一个n
我们输出第n个小朋友的年龄
大家不难看出这个题目中
这事情的规律
显然这是一个数值问题
每一个小朋友的年龄
都是他前面小朋友年龄
再加上两岁
所以
很容易就把这个问题表达成
屏幕上大家看到的这个数学公式
那对数值型问题来说
找到了数学公式
接下来
就是如何找到递归结束的条件
也很显然
当n为1的时候
这个小朋友的年龄是10岁
递归结束的条件就是
当n为1时
函数值为10
根据以上的分析
我们就可以写出
这个递归的函数
大家看
我们定义一个整型的函数
函数名就叫年龄
一个整型变量n
为函数的形参
当n的值为1的时候
函数返回值为10
就是第一个小朋友的年龄
否则
函数返回值为
函数的自身调用
而是缩小了规模
再加上2
这个程序比较简单
我们从这就可以看到
在主函数内输入一个n的值
主函数内输一个n的值
在这我们定义一个整型变量k
让这个k
来存放小朋友的年龄
下面我们就
运行一下看看
我们把刚才那段程序
录入进来
首先我们就输入这个
递归的函数
在这个函数中
如果
n的值为1
我们就返回10
第一个小朋友的年龄
否则
就返回
函数的递归调用
再加2
这个就是
递归函数
接下来我们再编写主函数
在主函数里
咱们定义一个k
用来存放小朋友的年龄
从键盘
输入一个整型变量的值
输给n
我们把
用n为实参
调用这个函数的结果
赋给整型变量k
然后输出
看一下
这个
第
n号小朋友的年龄
是多少呢
是我们调用函数结果返回之后
获得的k
这个程序写完了
保存
编译
运行
现在我们输入第几个小朋友呢
比如输入第一个小朋友
从题目我们知道
这个小朋友的年龄是10岁
咱们运行输入第
3个小朋友
这个小朋友年龄是14岁
下面我们来看第二个练习
用递归方法
计算下面这个函数的值
当n大于0的时候
函数p(x)等于
按照这个规律
函数中的每一项
都是x的幂函数
但是符号是正负交替的
显然这是一个数值类的问题
解决这类问题的思路是
首先要找到
能够描述递归关系的
一个数学公式
那么我们来看
现在
函数中的这一连串的
表达式
我们是否可以发现其中的规律
那么第一
每一项都有x
咱们把x先提出来
然后原表达式就变成了
我们把括号中再做一次变换
就可以将原表达式变成
再用括号括起来
就变成
相信大家都发现了
括号内的表达式
很想原来的最开始的
函数表达式
那大家一定想起来
我们这一章最开始的时候说
从前有个山
山里有个庙
庙里有个老和尚讲故事
讲的什么呢
讲的还是
从前有个山 山里有个庙
庙里有个老和尚讲故事
这就是递归
那现在我们就不难看出
函数px就等于
x乘
1减去这个函数的自身调用
只是函数的规模缩小了
以上就是这个递推公式
接下来我们知道
这个递归的边界条件是
当n的值为1的时候
函数值为1
通过以上的分析
我们找到了
解决这个递归问题的
数学公式和边界条件
接下来咱们就编写这个程序
并且运行
我们首先编写这个递归函数
我们定义这个函数
px为double型
函数的形参
是一个double的x
和一个整型的n
在函数体内部
首先我们知道
这个递归的边界条件是
当n的值为1的时候
函数的返回值为1
否则
函数的返回值为x
乘上
括号的1减去
这个函数的自身的调用
此时的参数是x和n-1
也就是说
函数自身调用
但是规模缩小了
我们可以把这段注释写上
此时为
函数的自身调用
那么这段功能函数
就完成了
接下来我们来写
主函数
在主函数中咱们定义
整型变量n
一会我们要求前n项
然后我们定义double型的x
定义一个
snm
代表了一会我们求的和
然后咱们从键盘
按照double型的格式
和
整数的形式
来输入x的值
输入n的值
我们把
以x和n为实参
调用递归函数px的返回值
赋给sum变量
然后我们输出
我们显示
这个前n项的和
是
就是我们求得的
sum
在这我们设置一下格式
以整数的方式输出
主函数写完了
我们在这
在这可以增加一个注释
说明一下此时
计算
这个函数前n项的和
保存
大家看到这个就是
一个完整的程序
我们现在编译
运行
首先咱们输入一个1
求前十项
大家可能不难分析
这个结果是几呢
1的平方
立方
四次方
都是1
在整个这个函数中
我们刚才回顾一下
是正负交替的
前十项的结果为0
接下来我们再运行一下
咱们现在输一个2
然后也来看一下它的前十项
大家看到运行的结果为
负170
刚才的两个练习
都是解决的数值类的递归问题
现在咱们再来看
屏幕这个问题
反向输出给定的整数
比如
当从键盘输入12345的时候
我们希望输出54321
显然这是一个非数值型的问题
解决这类问题的
首要的思路是
要找到解决问题的
具体的操作步骤
也就是说
找到明确的解法
第二
是将原来的问题
找到性质相同的小问题
有了这样的分析
接下来咱们看
具体到这个题
我们该以什么样的思路
来设计程序
首先
如果我们有一个整数
有什么办法
能够得到这个整数的个位呢
大家想想
前面学过的运算符中
哪个运算符能够帮助我们
求得整数的个位数
求余
当我们得到各位之后
接下来
我们怎么样去把原来的问题
规模缩小
一个整数原来五位
现在我们希望得到前四位
除10
原来问题缩小之后
接着
对缩小了的问题再进行
个位的输出
以此类推
接着我们就要判断结束条件
如果满足了
递归结束的条件
就结束这个递归算法
否则转向第一步
继续运行
接下来我们就详细的分析一下
这个问题的运行过程
大家看
如果我输入了
12345
作为一个递归函数
将怎样来解决这个问题呢
比如
我们以整数n作为参数
现在n的值是12345
刚才说了
递归的条件对这个问题来说
如果n大于10
比如15 比如18
我们需要取出它的个位
那我们就设法
找到它的个位
比如找到这个5
然后我们输出最后这一位
比如我们得到了个位
然后我们让这个n除以10
取整
得到一个缩小了的
整数
我们得到的是1234
然后我们对这个1234
再做反向的输出
也就是说
又去调用这个函数
只是规模缩小了
于是再来判断
n大于等于10
满足
于是输出最后一位
继续
再除10
得到了缩小了的规模的数
也就是一个三位的
然后再调用
最后
当
缩小到只剩一位的时候
不满足n大于等于10的条件了
于是
输出n本身
我们就得到了一个
将原有的数
反向输出的结果
这样的一个思路
大家注意
关键在于首先
如何将问题缩小
第二
如何来控制递归的结束
这是编写递归程序的关键
下面我们就来看
这个问题的完整的程序
在主函数中
咱们定义整型变量x
对被调函数作说明
从键盘输入一个整型
数据
赋给x
以x为实参
调用
反序的这个函数
那么在被调函数中
x的值传给了
被调函数的形参n
判断递归条件
当n大于等于10的时候
那么我们用
取余这个运算符
就得到了当前整数的个位
然后调用
这个反序的函数
但是参数变成了
n除10
于是将原问题缩小了
函数自身调用
屡次一一输出
当前整数的最后一位
就是个位
的时候
不断的缩小规模
直到n小于10
也就是说
递归达到了
递归条件的结束的时候
我们只需要输出这个n本身
就可以了
以上就是我们做了一些练习
接下来请大家思考
如果要求用递归方法
求两个整数
m和n的最大公约数
我们该怎么做
我们以前学循环时候
大家很容易编出
1到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