递归练习
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
:递归就是自己调用自己,也就是重复的思想。
1. 求1+2+3+……+n的值
#include "stdio.h"
int fun(int num)
{
int sum=0;
if ( num==1)
sum=1;
else
sum=num+fun(num-1);
return sum;
}
2. 求1*2*3*……*n的值。
#include "stdio.h"
int fun(int num)
{
int product;
if ( num==1)
product=1;
else
product =num*fun(num-1);
return product;
}
3. 著名的菲波拉契(Fibonacci)数列,其第一项为0,第二项为1,从第三项开始,其每一项都是前两项的和。如:1 1 2 3 5 8 13。。。。。。。。。。。。编程求出该数列前N项数据。
非递归求解:
解法一:数组迭代
#include
void main( )
{
long f[50];
int i;
f[0]=0;
f[1]=1;
for(i=2;i<20;i++) //生成第3~20项菲波拉契数列
f[i]=f[i-1]+f[i-2];
for(i=0;i<20;i++) //输出前20项的菲波拉契数列
printf("f[%d]=%d\n",i,f[i]);
}
解法二: 变量替换,又额外申请了变量f0,f1,f2,每次更新相加的数。
#include
void main()
{
int f0=0,f1=1,f2;
for(int i=2;i<20;++i)
{
f2=f0+f1;
f0=f1;
f1=f2;
printf("f[%d]=%d\n",i,f2); //输出第3~20项的菲波拉契数列
}
}
递归求解:
#include
int fbi(int n)
{
if(n==1) return 0;
if(n==2) return 1;
if(n>2) return fbi(n-1)+fbi(n-2);
return -1;
}
void main()
{
int x;
for(int i=1;i<=20; i++) //输出前20项的菲波拉契数列
printf("f[%d]=%d\n",i,fbi(i));
}
4. 输入一个整数,求这个数的各位数字之和。
非递归求解:
#include
int main()
{
int num = 0;
int s = 0;
int i = 0;
printf("请输入一个整数:");
scanf("%d", &num);
while(num)
{
s += num%10;
num = num/10;
i++;
}
printf("数字个数为%d,各个数相加为%d\n",i, s );
return 0;
}
递归求解:
#include
int sum(int n)
{
if(n==0)
return 0;
else
return n%10+sum(n/10);
}
void main()
{
int n;
printf("请输入一个整数:");
scanf("%d",&n);
printf("%d\n",sum(n));
}
5. 求两个数的最大公约数。
非递归求解:
#include "stdio.h"
long gys(int a,int b)
{
int r;
while(b!=0)
{
r=a%b;
a=b;
b=r;
}
return a;
}
void main(void)
{
int a,b;
scanf("%d%d",&a,&b);
printf("最大公约数为:%d\n",gys(a,b));
}
递归求解:
#include
int gys(int a,int b)
{
int r;
r=a%b;
if(r==0) return b;
else return gys(b,r);
}
void main(void)
{
int a,b;
scanf("%d%d",&a,&b);
printf("最大公约数为:%d\n",gys(a,b));
}
6. 求整数n的倒数第x位数。
非递归求解:
#include "stdio.h"
int fnk(int n, int k)
{
if(n<=0) return -1;
while(k > 1)
{
n = n / 10;
k --;
}
return n % 10;
}
void main(void)
{
int a,b;
a = 123456;
b = 3;
printf("fnk(%d, %d) = %d", a, b, fnk(a, b));
}
递归求解:
#include "stdio.h"
int fnk(int n, int k)
{
if((n <=0) || (k <= 0) ) return -1;
if(k == 1 && n>0) return n%10;
return fnk(n/10, k-1);
}
void main(void)
{
int a,b;
a = 123456;
b = 3;
printf("fnk(%d, %d)=%d", a, b, fnk(a, b));
}
7.
递归求解:
#include "stdio.h"
#include "math.h"
double fxn(int x, int n)
{
if(n==1) return sqrt(1+x);
else return sqrt(n+fxn(x,n-1));
}
void main(void)
{
int a,b;
a=1;
b=2;
printf("fxn(%d, %d)=%f", a, b, fxn(a, b));
}
非递归求解:
#include "stdio.h"
#include "math.h"
double fxn(int x, int n)
{
double f;
int i=1;
f=sqrt(i + x);
while (++i<=n)
{
f=sqrt(i+f);
}
return f;
}
void main(void)
{
int a,b;
a=1;
b=2;
printf("fxn(%d, %d)=%f", a, b, fxn(a, b));
}