同一个问题的循环程序与递归程序实现的比较
2022-12-06朱子楠
张 竞 朱子楠 梁 晗 张 丽
咸阳师范学院计算机学院 陕西咸阳 712000
比较方法是指确定对象之间差异点和共同点的逻辑方法，是人类认识事物的一种基本思维方法。人们根据一定的需要和标准，把彼此有某种联系的事物加以分析、对比，从而找出它们的内在联系、共同规律和特殊本质的一种方法。客观事物的相互联系又相互区别是比较方法的客观基础。[1]马克思曾经说过“比较方法是理解现象的钥匙”。[2]
在C语言程序设计课程的教学过程中，学生通过对同一个问题设计其循环程序与递归程序的比较，使学生亲身体验循环程序与递归程序的不同，真正深刻地认识到循环程序与递归程序各自的优点，引导学生更深入的认识循环程序与递归程序，激发学生学习循环程序与递归程序的浓厚兴趣。[3]
1 计算数列的第n项an
例1-1 计算数列a，aa，aaa，aaaa，aaaaa，…的第n项an。[4]
方法1 使用循环程序实现
#include
int aaa(int a,int n)
{ int k, an=0;
if(n==1) an = a;
else for(k=1; k<=n; k++) an = an*10+a;
return an;
}
int main()
{ int a,n,an;
printf("a n = ");
scanf("%d%d",&a,&n);
an = aaa(a,n);
printf("an = %d ", an);
return 0;
}
方法2 使用递归程序实现
#include
int aaa(int a,int n)
{ if(n==1) return a;
else return aaa(a,n-1)*10+a;
}
int main()
{ int a,n,an;
printf("a n = ");
scanf("%d%d",&a,&n);
an = aaa(a,n);
printf("an = %d ", an);
IRF2是IFN信号通路的重要组成成分，在其信号通路中IRF2与其它调节因子共同调控细胞周期，在对肿瘤的调控中具有不可忽视的作用，通过对IRF2结构和功能的研究，我们发现，IRF2对免疫细胞的增值具有促进作用，可以通过提高IRF2的表达水平来增强机体抵御外界病毒的能力，从而减少机体患病的可能，并在某些疾病发生之初就能有效的应对。而且IRF2与IRF1具有竞争性抑制作用，可以利用这一点对癌症进行抑制，但是由于其对癌症的双重作用，我们可以尝试利用蛋白的构象改变对其进行进一步研究，以希望能尽早的征服癌症，研发出对癌症有效的药物。
return 0;
}
例1-2 计算斐波那契数列1，1，2，3，5，8，13，21，34，55，…的第n项an。[5]
方法1 使用循环程序实现
#include
int fib(int n)
{ int k, a1=1,a2=1,an ;
if(n==1 || n==2) an = 1;
else for(k=3; k<=n; k++)
a1 = a2;
a2 = an;
}
return an;
}
int main()
{ int n,an;
printf("n = ");
scanf("%d",&n);
an = fib(n);
printf("an = %d ", an);
return 0;
}
方法2 使用递归程序实现
#include
int fib(int n)
{ if(n==1 || n==2) return 1;
else return fib(n-1)+fib(n-2);
}
int main()
{ int n,an;
printf("n = ");
scanf("%d",&n);
an = fib(n);
printf("an = %d ", an);
return 0;
}
2 计算数列的前n项和sn
例2-1 计算自然数列1，2，3，4，5，6，7，…的前n项和sn。[6]
方法1 使用循环程序实现
#include
int sum(int n)
{ int k,sn=0;
for(k=1;k<=n;k++) sn=sn+k;
return sn;
}
int main()
{ int n,sn;
printf("n = ");
scanf("%d",&n);
sn = sum(n);
printf("sn = %d ",sn);
return 0;
}
方法2 使用递归程序实现
#include
int sum(int n)
{ if(n==1) return 1;
else return sum(n-1)+n;
}
int main()
{ int n,sn;
printf("n = ");
scanf("%d",&n);
sn = sum(n);
printf("sn = %d ",sn);
return 0;
}
例2-2 计算等差数列a1,a1+d,…,a1+(n-1)*d,…的前n项和sn。[7]
方法1 使用循环程序实现
#include
int sum(int a1,int d,int n)
{ int k,ak,sn=0;
for(k=1;k<=n;k++)
{ ak=a1+(k-1)*d;
sn=sn+ak;
}
return sn ;
}
int main()
{ int a1,d,n,sn;
printf("a1 d n = ");
scanf("%d%d%d",&a1,&d,&n);
sn = sum(a1,d,n);
printf("sn = %d ", sn);
return 0;
}
方法2 使用递归程序实现
#include
int sum(int a1,int d,int n)
{ if(n==1) return a1;
else return sum(a1,d,n-1) + a1+(n-1)*d;
}
int main()
{ int a1,d,n,sn;
printf("a1 d n = ");
scanf("%d%d%d",&a1,&d,&n);
sn = sum(a1,d,n);
printf("sn = %d ", sn);
return 0;
}
3 计算最值
例3-1 计算两个整数a和b的最大公约数gcd。[8]
方法1 使用循环程序实现
#include
int gcd(int a,int b)
{ int r=a%b;
while(r!=0)
{ a=b;
b=r;
r=a%b;
}
return b;
}
int main()
{ int a,b;
printf("a b = ");
scanf("%d%d",&a,&b);
printf("gcd = %d ",gcd(a,b));
return 0;
}
方法2 使用递归程序实现
#include
int gcd(int a,int b)
{ if(a%b==0) return b;
else return gcd(b,a%b);
}
int main()
{ int a,b;
printf("a b = ");
scanf("%d%d",&a,&b);
printf("gcd = %d ",gcd(a,b));
return 0;
}
例3-2 计算两个整数a和b的最小公倍数lcm。[9]
方法1 使用循环程序实现
#include
int gcd(int a,int b)
{ int r=a%b;
while(r!=0)
{ a=b;
b=r;
r=a%b;
}
return b;
}
int main()
{ int a,b;
printf("a b = ");
scanf("%d%d",&a,&b);
printf("gcd = %d ",gcd(a,b));
printf("lcm = %d ",a*b/gcd(a,b));
return 0;
}
方法2 使用递归程序实现
#include
int gcd(int a,int b)
{ if(a%b==0) return b;
else return gcd(b,a%b);
}
int main()
{ int a,b;
printf("a b = ");
scanf("%d%d",&a,&b);
printf("gcd = %d ",gcd(a,b));
printf("lcm = %d ",a*b/gcd(a,b));
return 0;
}
有比较才有鉴别，做比较才可能有更深刻地认识。循环程序与递归程序的比较如下：
序号比较项目循环方法递归方法1操作对象递归数列递归数列2使用的语句循环语句递推语句3递推方法人为的递推自动的递推
