参考链接： C 程序使用递归查找GCD
一、心得感悟
关于函数之前有过总结，函数是在编程中为简化主程序、使复杂程序简单化的子程序。而递归函数则是一种特殊的函数。它是直接或间接调用的函数，通常可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。递归策略只需少量的程序就可以描述出解题过程所需要的多次重复计算。大大减少了程序的代码量。递归的能力在于有限的语句来定义对象的无限集合。用递归思想写出的程序往往十分间接易懂。总而言之，使用递归函数是解决大型复杂问题必不可少的。
二、内容总结及例题
下面结合部分代码来简介一下递归函数。
例如
1.求x^n。首先可以把x^n分解成：
x^0=1 （n=0）
x^1=x*x^0（n=1）
x^2=x*x^1（n=2）
x^3=x*x^2（n=3）
……
因此将x^n转化为：x*x^n-1，其中求x^n-1又用求x^n的方法进行求解。
分析：
<1>.定义子程序xn(int n)求x^n；如果n>=1，则递归调用xn(n-1)求x^n-1;
<2>.当递归调用到达n=0时终止调用。然后执行本“层”的后继语句；
<3>.遇到子程序运行完后，就结束本次的调用，返回到上一“层”调用语句的地方，并执行其后继语句；
<4>.继续执行步骤3，从调用中逐“层”返回，最后返回到主程序。
程序如下：
#include<iostream>using namespace std;int xn(int);//定义递归函数int x;int main(){ int n; cin>>x>>n; cout<<x<<'^'<<n<<"="<<xn(x)<<endl; return 0;}int xn(int n){ if(n==0)return 1; //递归边界 else return x*xn(n-1); //递归式
}
2.求x!
x!={ 1 (x=0)
x(x-1) (x>0)
}
分析x!=x(x-1)!,其中求(x-1)!仍采用求x!的方法，需要定义一个求x!的函数，逐级调用此函数，即：
当x=0时，x!=1；当x>0时，x!=x*(x-1)。
假设用函数f(x)表示x的阶乘，当x=3时，f(3)的求解方法可表示为：f(3)=3*f(2)=3*2*f(1)=3*2*1*f(0)=3*2*1*1=6
<1>.定义函数：int f(int n)
如果n=0，则f=1；如果n>0，则继续调用函数f=n*f（n-1）;
<2>.返回主程序，打印f(x)的结果。
程序如下：
#include<iostream>using namespace std;int f(int);int main(){ int x; cin>>x; cout<<x<<"!="<<f(x)<<endl;//主程序调用f(x)求x！ return 0;}int f(int n) //函数f(n)求n！{ return n==0?1:n*f(n-1); //调用函数f(n-1)递归求(n-1)!
}
3.用递归方法求m,n两数的最大公约数。（m>0,n>0）
求两个数的最大公约数，这里用辗转相除法。
<1>.求m除以n的余数；
<2>.如果余数不为0，则让m=n,n=余数，重复步骤<1>,即调用子程序；
<3>.如果余数为0，则终止调用子程序；
<4>.输出此时的n值。
程序如下：
#include<iostream>using namespace std;int gcd(int,int);int main(){ int m,n; cin>>m>>n; cout<<"gcd="<<gcd(m,n)<<endl; return 0;}int gcd(int m,int n){ return n==0?m:gcd(n,m%n);
}
4.把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
本题我认为是有难度的题目，它涉及多种情况谈论，少一种题目就会错误。
设f(m,n)为m个苹果，n个盘子的放法数目，则先对n作讨论，
当n>m：则必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即 if(n>m) f(m,n) = f(m,m)
当n <= m:不同的放法可以分成两类：含有0的方案数，不含有0的方案数
<1>.含有0的方案数，即有至少一个盘子空着，即相当于 f(m,n)=f(m,n-1);
<2>.不含有0的方案数，即所有的盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n)=f(m-n,n).而总的放苹果的放法数目等于两者的和，即 f(m,n)=f(m,n-1) f(m-n,n)
代码如下：
#include<bits/stdc .h>using namespace std;int fun(int m,int n) //m个苹果放在n个盘子中共有几种方法{ if(m==0||n==1) //当m==0(没有苹果可放)时，定义为1种放法； return 1; //当n=1时，所有苹果都必须放在一个盘子里，所以返回1； if(n>m) return fun(m,m); else return fun(m,n-1) fun(m-n,n);}int main(){ int T,m,n; cin>>T; while(T--) { cin>>m>>n; cout<<fun(m,n)<<endl; } return 0;
}
