《C编程技巧：117个问题解决方案示例 》 —3.4　使用递归计算斐波那契数列

3.4　使用递归计算斐波那契数列

问题

你想使用递归计算斐波那契数列。

解决方案

编写一个C程序，使用具有以下规格说明的递归计算斐波那契数列：

程序应计算前N个斐波那契数。

程序由一个名为fib()的用户定义函数组成，该函数递归调用自身以计算斐波那契数。

在屏幕上显示计算出的斐波那契数。

代码

以下是使用这些规格说明编写的C程序的代码。在文本编辑器中键入以下C程序，并将其保存在文件夹C:\Code中，文件名为fibona2.c：

编译并执行此程序。这个程序的运行结果在这里给出：

工作原理

此程序计算前N个斐波那契数。跨越LOC 6～9的do-while循环接受数字N的值，并将其赋值给int类型变量intN。跨越LOC 11～15的for循环计算N个斐波那契数。LOC 13在屏幕上显示计算出的斐波那契数。LOC 13还使用输入参数intK调用函数fib()。函数fib()在LOC 19～27中定义。在LOC 26中，对该函数进行两次递归调用。在第一次递归调用中，输入参数的值减1，而在第二次递归调用中，输入参数的值减少2，在连续的递归调用中，输入参数的值继续减小，并且当它变为0或1时，返回第一和第二个斐波那契数的标准值，如LOC 21～24所示。