递归程序设计

一．赶鸭子
1.题目分析
一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
2.算法构造
递归出口v=7;
递归函数duck（）；
原来的鸭子总数Sum=(duck(v+1)+1)*2;
每经过一个村庄卖掉的鸭子数sell=sum-duck(i);
3.算法实现
递归：
#include<stdio.h>
int duck(int v)
{
if(v==7)
return 2;
else
return (duck(v+1)+1)*2;
}
int main()
{
int sum=duck(0);
int sell=0;
printf(“出发时共赶%d只鸭子\n”,sum);
for(int i=1;i<=7;i++)
{
sell=sum-duck(i);
sum=duck(i);
printf(“经过第%d个村子卖出鸭子： %d\n”,i,sell);
}
return 0;
}

非递归：
#include<stdio.h>
int main()
{
int sum=2;
int v=7;
while(v>0)
{
sum=(sum+1)*2;
v–;
}
printf(“出发时共赶%d只鸭子\n”,sum);
return 0;
}
4.调试、测试及运行结果
递归：

非递归

二.角谷定理
1.题目分析
角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
如：输入22，
输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
STEP=16
2.算法构造
step记录经过了几个数即运行步数，
通过if判断奇数还是偶数，
for循环直至为1.
3.算法实现
#include<stdio.h>
void main()
{
int a=0;
int step=1;
printf(“输入一个自然数:”);
scanf("%d",&a);
for(int i=0;i<step;i++)
{
if(a1)
{
printf("%d\n",a);
}
else if(a%20)
{
printf("%d\n",a);
step++;
a=a/2;
}
else if(a%2!=0)
{
printf("%d\n",a);
step++;
a=a*3+1;
}
}
printf(“step=%d\n”,step);

}
4.调试、测试及运行结果