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的自然数之和

那现在

我们怎么样用递归的方法

来实现这个功能