《程序设计方法学》实验报告 - 1 -
1、实验内容或题目：
（1）从以下四小题中，选择两个给予递归实现。
计算两个整数X、Y的最大公约数
求Fibonacci数列的前n项。
McCarthy91函数的求解
Ackermann函数的求解
（2）用良序归纳法，证明所选择的递归程序的正确性
2、目的与要求
掌握迭代与递归的概念、迭代程序与递归程序的关系;理解函数型递归程序模型，掌握函数型递
归程序的常见计算规则(如最左最内规则、平行最外规则等); 理解、掌握证明递归程序正确性的结
构归纳法和良序归纳法。
3、实验步骤与源程序（若此部分）：
㈠实验步骤：
（1） 用C/C++/Java，编写完整的递归程序
（2） 设计几组数据，首先用常见的递归程序的计算规则，手工计算函数的预期结果，然后运
行调试程序，观察输出结果。直至输出结晨与预期结果吻合。
（3） 证明以上递归程序的正确性。
㈡源程序：
①求Fibonacci数列的前n项：
#include <iostream.h>
int Fibonacci(int n)
{
if (n==0) return 0;
else if (n==1) return 1;
else return (Fibonacci(n-1)+Fibonacci(n-2));
}
void main()
{
//求斐波那契数列的第n项和前n项之和
int n,m,l;
m=0;
cout<<"请输入n值：";
cin>>n;
cout<<"\n";
cout<<"斐波那契数列:"<<endl;
for (int i=0;i<=n;i++)
{
m=m+Fibonacci(i);
l=Fibonacci(i);
cout<<l<<" "<<endl;
}
