8.5 函数的递归调用

考点6 函数的递归调用

真考链接

针对考点6的考查出现在选择题的读程序题中。程序涉及函数的递归调用。考点6属于重点理解重点掌握的内容，难度偏难。考核概率为90%。在操作题中的考核概率为10%。

在调用一个函数的过程中又出现直接或间接地调用该函数本身的，称为函数的递归调用。允许函数的递归调用是C语言的特点之一。

当一个问题在采用递归法解决时，必须符合以下3个条件：

（1）可以把要解决的问题转化为一个新的问题。而这个新问题的解决方法仍与原来的解决方法相同，只是所处理的对象有规律地递增或递减。

（2）可以应用这个转化过程使问题得到解决。

（3）必须要有一个明确的结束递归的条件。

当函数自己调用自己时，系统将自动把函数中当前的变量和形参暂时保留起来，在新一轮的调用过程中，系统将为本次调用的函数所用到的变量和形参开辟新的存储单元。因此，递归调用的层次越多，同名变量所占的存储单元也就越多。当本次调用的函数运行结束时，系统将释放一次调用所占的存储单元。当程序执行的流程返回到上一层的调用点时，同时取用进入该层函数中的变量和形参所占用的存储单元中的数据。

小提示

在函数的递归调用过程中，并不是重新复制该函数，只是重新使用新的变量和参数。每次递归调用都要保存旧的参数和变量，使用新的参数和变量，当递归调用返回时，再恢复旧的参数和变量。

在使用函数的递归调用和嵌套调用时，一定要清楚其中的逻辑关系，否则容易造成程序的混乱。

常见问题

如果没有正确的递归结束条件，程序会出现什么问题？

在编写递归函数时，必须建立递归结束条件，使程序能够在满足一定条件时结束递归并逐层返回。如果没有正确的递归结束条件，在调用该函数进入递归过程后，就会无休止地执行下去而不会返回。

真题精选

【例1】以下程序的输出结果是（　　）。

＃include ＜stdio.h＞

int func（int n）

｛ if（n==1）

return 1；

else

return（n*func（n-1））；

｝

main（）

｛ int x；

x=func（3）；

printf（＂% d\n＂，x）；

｝

A.5　　　　B.6　　　　C.7　　　　D.8

【答案】B

【解析】func（）是递归函数，func（3）=3*func（2）=3*2*func（1）=3*2*1=6。

【例2】以下程序的输出结果是（　 ）。

＃include ＜stdio.h＞

long fun（int n）

｛ long s；

if（n==1||n==2）

s=2；

else

s=n+fun（n-1）；

return s；

｝

main（）

｛ printf（＂\n% ld＂，fun（4））；

｝

A.7　　　　B.8　　　　C.9　　　　D.10

【答案】C

【解析】此题考查基本的函数递归调用方法。程序在n=1或n=2时是出口条件，不再递归，否则一直执行s=ns+fun（n-1）的操作。展开此求和公式，有s=4+fun（3）=4+3+fun（2）=4+3+2=9。如果调用函数fun（）的实参大于等于2，出口n==1的判断就不需要了。

【例3】下列给定程序中函数fun的功能是：用递归算法计算斐波拉契数列中第n项的值。从第1项起，斐波拉契数列为1、1、2、3、5、8、13、21、…

例如，若给n输入7，则该项的斐波拉契数值为13。

请改正程序中的错误，使它能得出正确的结果。

注意：不要改动main（）函数，不得增行或删行，也不得更改程序的结构。

试题程序

＃include ＜stdio.h＞

long fun（int g）

｛ ／*****found*****／

switch（g）；

｛ case 0：return 0；

／*****found*****／

case 1；case 2：return 1；

｝

return（fun（g-1）+fun（g-2））；

｝

void main（）

｛ long fib；int n；

printf（＂Input n：＂）；

scanf（＂% d＂，&n）；

printf（＂n=% d\n＂，n）；

fib=fun（n）；

printf（＂fib=% d\n\n＂，fib）；

｝

【答案】（1）去掉分号 （2）case1：case2：return 1；

【解析】本题考查：switch语句，其一般形式如下：

switch（表达式）｛

case常量表达式1：语句1；

case常量表达式2：语句2；

…

case常量表达式n：语句n；

default：语句n+1；

}

其中switch（表达式）后不应该带有“；”，同时case语句常量后应该是“：”。

C语言中，switch语句之后不能有分号，并且case语句常量后应用的是冒号。