5.4　函数的递归调用

5.4　函数的递归调用

在调用函数的过程中又直接或间接地调用该函数本身,称为函数的递归调用。

例5-4 有4个学生在操场跑步,第1个学生跑了2圈,第2个学生比第1个学生多跑了3圈,第3个学生比第2个学生多跑了3圈,第4个学生比第3个学生多跑了3圈,求第4个学生跑了几圈?

分析:

要求解第4个学生跑了几圈,需要先求出第3个学生跑了几圈。

要求解第3个学生跑了几圈,需要先求出第2个学生跑了几圈。

要求解第2个学生跑了几圈,需要先求出第1个学生跑了几圈。

第1个学生跑了2圈是已知的,这就不难求出第2个学生跑的圈数。

假设每个学生跑的圈数定义为函数circle,由此可以推导出如下关系式:

4个同学所跑圈数可以由图5-4所示。

程序如下:

图5-4　关系图

例5-5 有n筐梨排成一排,第1筐梨有2个,第2筐是第1筐梨个数的2倍多1个,第3筐是第2筐梨个数的2倍多1个,依次类推。求出第10筐梨的个数。

分析:

假设求第i框梨的函数定义为pear,那么有如下关系式:

程序如下:

例5-6 一群猴子第一天摘了一堆桃子,当天猴子把桃子吃了一半,但还想吃,就又多吃了两个,第二天,猴子吃了剩下桃子的一半,但还想吃,又多吃了两个,以后猴子每天都吃掉前一天剩下桃子的一半多两个,到第5天猴子再想吃时,只剩下两个桃子了。试编程实现求解第一天共摘了多少个桃子?

分析:

第一天摘得桃子总数是未知的,但是最后一天即第5天剩的桃子是已知的——两个,而且又知道每天吃的桃子是前一天剩的桃子的一半多两个。

假设,每天的桃子数定义为int sum(int day);,当day==5时,sum(5)=2;,这样可以推算出第4天的桃子总数为:(https://www.daowen.com)

sum(4)=2×(sum(5)+2)

第三天桃子总数为:

sum(3)=2×(sum(4)+2)

第二天桃子总数为:

sum(2)=2×(sum(3)+2)

第一天桃子总数为:

sum(1)=2×(sum(2)+2)

由此可以得到下面的表达式:

因此可以用递归的方法去编写程序,程序设计如下:

程序运行结果为:

第一天摘的桃子总数为:92

这样,可求得第一天摘的桃子数为92个。

除了这种方法,还可以考虑用之前学过的循环结构来解决例5-6。

分析:

假设第五天剩的桃子sum(5)=2,第四天的桃子总数sum(4)=(sum(5)+2)×2,然后用第四天的桃子数sum(4)去推算第三天的桃子数sum(3),依此类推,因为共5天,所以要推算4次,即可求出第一天的桃子总数。

程序如下:

或者直接将括号中的day＞0改为day--,循环语句中的day--就可以删除了。因为day从4开始,执行4次循环后,day的值为0,循环语句不再执行,即可推算出第一天的桃子总数。

因为while循环和for循环是等价的,因此上述程序可以改为用for循环来实现,程序如下: