递归程序设计方法及实例
实例1：一个人赶着鸭子去每个村庄卖，每经过一个村子卖去所赶鸭子的一半又一只。这样他经过了七个村子后还剩两只鸭子，问他出发时共赶多少只鸭子？经过每个村子卖出多少只鸭子？
//卖鸭子#include<stdio.h>int num(int sum,int day);int main(){int s=num(2,8); //第七天还剩余鸭子2只printf("鸭子总数为%d只\n\n",s);for(int day=1;day<=7;day++) //输出每天卖出的鸭子数{printf("第%d天卖出%d只\n",day,s/2+1);s=s/2-1;}return 0;}int num(int sum,int day){if(day==1)return sum;elsereturn num((sum+1)*2,day-1); //递归计算鸭子数return 0;}
实例2：角谷定理。输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。求经过多少次可得到自然数1。
如：输入22，
输出 22 11 34 17 52 26 13 40 20 10 5 16 8 4 1
//角谷定理
#include<stdio.h>
int step;
int calculate(int a);
int main()
{
int a; //输入的自然数a
printf("请输入一个自然数:");
scanf("%d",&a);
calculate(a);
return 0;
}
int calculate(int a)
{
printf("%6d",a);
if(a==1)
printf("\nStep is %d\n",step+1);
else
{
if(a%2==0) //输入的自然数为偶数
{
a=a/2;
step++; //每计算一次,step加1
calculate(a); //递归调用
}
else if(a%2!=0) //输入的自然数为奇数
{
a=a*3+1;
step++;
calculate(a);
}
}
return 0;
}
实例三：电话号码对应的字符组合：在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。
//电话号码对应字符组合
//假设此程序中,0和1对应的英文字母分别为'*','#'
//做出此假设的原因是因为0和1没有对应的英文字母
#include<stdio.h>
#define M 12
#define N 30
int a[M]; //a[M]存储电话号码每位上的数字
char b[28]={'*','#','A','B','C','D','E','F','G','H','I','J','K','L','M','N',
'O','P','Q','R','S','T','U','V','W','X','Y','Z'}; //b[M]存储每个数字对应的不同的英文字母
char c[10][10] = { //用字符数组存储每个数字对应的不同英文字母
'*', '#', "ABC", "DEF",
"GHI", "JKL", "MNO",
"PQRS", "TUV", "WXYZ"};
int i,n;
int GroupNum(int x);
int main()
{
printf("请输入电话号码的总位数:");
scanf("%d",&n);
for(i=0;i<n;i++)
{
printf("请输入电话号码的第%d位:",i+1);
scanf("%d",&a[i]);
}
i=0;
printf("此电话号码对应的字符串组合共有%d组\n",GroupNum(1));
return 0;
}
int GroupNum(int x) //求总共组合数
{
if(i==n)
return x;
else
{
if(a[i]==0 || a[i]==1)
{
x=1*x;
i++;
GroupNum(x); //递归调用
}
else if(a[i]==2 || a[i]==3 || a[i]==4 || a[i]==5 || a[i]==6 || a[i]==8 )
{
x=3*x;
i++;
GroupNum(x);
}
else
{
x=4*x;
i++;
GroupNum(x);
}
}
}
实例4：日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完 后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？
//分桔子问题递归程序设计方法总结
#include<stdio.h>
// oldUNum为每个人原有桔子数，getNum为得到的桔子数,n为第几个人
int orangeNum(int oldNum,int getNum,int n);
int main()
{
//老大原有240个桔子，得到210个
orangeNum(240,210,1);
return 0;
}
int orangeNum(int oldNum,int getNum, int n)
{
int nextGetNum,nextOldNum,m;
if(n > 6) //递归出口
return 0;
else
{
printf(" 第%d个人原有桔子%d\n",n,oldNum); //输出原先橘子数
if(n == 1) //计算分给下一个人的橘子数
nextGetNum = oldNum/(9 - n);
else
nextGetNum = (oldNum+getNum)/(9-n);
nextOldNum = 2520/6* (8-n)/(7-n) - nextGetNum; //下一个人原来的橘子
m = n+1;
orangeNum(nextOldNum,nextGetNum,m);
}
return 0;
}
————常见递归问题的分析与设计
1.卖鸭子问题：这是常见的递归函数问题，求得一个递归函数公式即可。设计函数int num( int sum,int day);其中sum参数返回鸭子的数量,day参数返回第几天。编写递归程序的关键为确定递归出口和递归体。本题递归出口为当day==1时，return sum;递归体为当day!=1时，return num((sum+1)*2,day-1);同时在主函数中输出每天所卖的鸭子数目。
2.角谷定理：本题的设计思路比较简单，仍然为一个递归函数问题。按照题意，输入一个自然数，若为偶数，则把它除以2，若为奇数，则把它乘以3加1。经过如此有限次运算后，总可以得到自然数值1。得到递归结束出口为a==1;return总步数。递归体为当a==偶数时，自身除以二，并累加步数，返回calculate函数。当a为奇数时，自身乘三加一，并累加步数，返回calculate.
3.电话号码对应的字符组合：首先清楚2,3,4,5,6,8六个数字对应三个英文不同的字母，8,9三个数字对应4个不同的英文字母。由于数字1和0并没有对应的英文字母，所以假设0和1分别对应’*’,’#’,这种假设并不影响最后递归算法的设计。还可以增强程序的健壮性。
计算组合数：需要统计电话号码有几个数字，且每个数字对应几个英文字母。把每个数字对应的英文字母个数乘起来即为组合数。
计算具体的组合：需要统计具体哪几个数字，每个数字具体对应的英文字母是什么。逐一进行组合即可。
4.中村义作教授分桔子问题：这是一个环状互相关联的问题，想到应该使用递归来求解。首先应该分析得到已知和隐含条件。
最后桔子数目相等，则每人为420个。同时老大的身份最特殊，其余的人都是先得到再给出桔子，而老大是先给出后得到，并且最后为420个，由老六分给他210个桔子，则老大原来有240个桔子，老大原先有240个桔子，分出210个桔子，问题的突破口就找到了。设计函数orangeNum(oldNum,getNum,n);三个参数分别为原有桔子数，得到桔子数，和第几个人。将240,210,1三个参数传入后，就开始了递归函数的调用，当n>6时，递归调用结束。
递归问题总结：递归是程序直接或者间接调用自身的过程，递归模型由递归出口和递归体两部分组成，分析问题时主要要抽象出递归出口和递归体。递归问题一般分为两大类：一类是比较简单的数学上的递归函数，要求算得一个函数值，只需要将递归函数翻译出来即可。第二类为问题为一些实际的问题，没有统一的规律可循，解决问题的关键为充分的理解问题，发现问题中的已知和隐含条件。根据逻辑关系分析此问题为什么为一个递归问题，并由此得到递归出口和递归递归体，从而使问题得到解决。这类问题都比较复杂，需要进行大量的练习才能建立这种思维方式。