C语言编程入门:递归函数_c语言递归算法经典实例

函数有定义，有调用，定义函数是告诉系统函数有什么功能，调用就相当于要实现这个功能。

定义函数就相当于写剧本，告诉导演这个剧要演什么内容。

调用函数就是拍电影，把这个剧本的故事展现出来。

函数的定义语法格式：

数据类型 函数名( 形式参数表 )

{

函数体；

}

上述形式参数表是可选项，不是每个函数都有形式参数。

函数的调用语法格式：

函数名( );

或者：

函数名( 实际参数表 );

如果定义函数时没有形参，则调用时也没有对应的实参。

如果定义函数时有形参，则调用时也应该有对应的实参。

定义形参必须是变量，实参可以是常数，也可以是变量。

函数可以被别的函数调用，也可以调用别的函数。

1 函数的普通调用

我们来看一个简单的程序。

程序1：

函数f2调用了函数f1,主函数调用了函数f2。

程序运行结果：

当调用函数时，程序转到被调用函数，执行里面的语句，执行完毕再转到调用它的函数。

2 函数的递归调用

程序1中，函数f2调用函数f1，函数main调用函数f1。都是调用别的函数。

那么，当函数调用自己，则叫递归调用。

递归调用就是函数自己调用自己。

我们来看一个例子：

有5个人坐在一起，王老师问最右边那个人（我们称作第5个人）多少岁了？

这第5个人说他比坐在他左手边的人（我们称作第4个人）大2岁。

于是王老师就问第4个人多少岁？第4个人说坐在他左手边的人（我们称作第3个人）大2岁。

王老师问第3个人多少岁？第3个人说坐在他左手边的人（我们称作第2个人）大2岁。

王老师问第2个人多少岁？第2个人说坐在他左手边的人（我们称作第1个人）大2岁。

王老师问第1个人多少岁？第1个人看看他左边，没人了，只好回答他今年8岁。

问：第5个人多少岁？

我们计算第5个人的岁数，是不是要：

第5个人岁数 = 第4个人的岁数 + 2

第4个人的岁数 = 第3个人的岁数 + 2

第3个人的岁数 = 第2个人的岁数 + 2

第2个人的岁数 = 第1个人的岁数 + 2

第1个人的岁数 =8

递归函数就像上面这个套娃，一层套一层，直到找到最里面的那个套娃。

如果函数int age(int n)可以求出第n个人的岁数，则如果n等于1（第1个人），那么可以直接知道他的岁数是8岁。

如果n大于1，则第n个人的岁数等于第n-1个人的岁数+2。

如果我们用一个函数age(n)表示第n个人的岁数，那么上述公式可以表示为：

函数age有一个返回值，就是第n个人的岁数。

所以函数的类型为int，函数age定义如下：

return 返回一个整数值，返回第n个人的岁数。

当n等于1（第1个人），则返回8，否则返回前面那个人的岁数+2。

完整程序如下：

程序1：

程序1运行结果：

第5个人是16岁。

我们再来看一个例子，输入整数n，求n!

n！指n的阶乘，n的阶乘就是1乘以2乘以3乘以4一直乘到n的值。

这个程序用普通循环函数做，不用递归函数也可以实现。

我们先用普通函数实现。

程序2：

我们把求n!写在一个函数fact里，fact函数返回形参n的阶乘。

在主函数调用fact函数，比如求5的阶乘，则调用语句为: fact(5)。

但是求阶乘也可以用递归函数。

我们知道0的阶乘为1，1的阶乘也是1。

当n等于0或者n等于1时，n的阶乘为1。

如果n大于1，则n的阶乘等于n乘以(n-1)的阶乘。

所以求阶乘的公式为：

如果用函数fact(n)表示n的阶乘，那么上述公式可以表示为：

函数fact有一个返回值，就是第n的阶乘。

定义函数fact的类型为int，函数fact定义如下：

把程序2中的fact函数的定义改成递归函数，运行结果是一样的。

如果需要在主函数中输入整数，求这个整数的阶乘，可以写成：

程序3：

运行结果：

输入5，得出5的阶乘是120。

但是当输入的整数很大，比如输入整数是100时，我们看看运行结果：

如果是输入32，运行结果为：

100的阶乘是0，32的阶乘是负数？这明显不对呀。

这是因为，32的阶乘太大了，已经超出了int类型的取值范围，就产生了一个溢出错误。

这就相当于int类型的房间，所装的数有个最小最大范围的，超过这个范围，就没法装了，房间太小了，得换大的房间来装数，否则就会出现溢出错误。

所以这时我们应该把函数fact定义为double（双精度实型），这样就不会有问题了。

运行结果：

我们看到输出结果有6位小数，其实阶乘不会有小数，所以可以把程序中输出x对应的格式控制符%f改成%.0f就可以了，保留0位小数，即不要小数。

3 总结

函数可以调用任何函数，也可以调用自己。

自己调用自己的函数，叫递归函数。