递归算法总结
递归算法就是把一个大型复杂问题分解为小问题，而递归的关键就是找出递归定义和终止条件。
递归算法的解题步骤：
第一，分析问题，寻找大规模问题与小型问题的联系。
第二，控制递归，找出终止条件。
第三，设计函数，实现有关操作。
例如
1.求1-100的和
递归：f(n)=n+f(n-1);
终止条件：if(n==1)return 1;
函数实现
int f(int n)
{
if(n==1)return 1;
return f(n-1)+n;
}
2.辗转相除法的递归实现
int gcd(int m,int n)
{
if(n==0)return m;
return gcd(n,m%n)
}
3.快速幂实现
typedef long long ll;
ll f(ll int a, int b)
{
if(b%2)return (a*f(a,b-1));
ll n=f(a,b/2);//进行优化，减少计算次数
return n*n;
}
4.全排列问题
先把高位排好，再关注少一位的排列情况；
高位有若干种情况，就需要将问题化为多个子问题。每个子问题都与高位的排列有关；
要列举出所有高位的情况，以确定子问题；
需要离散枚举！
//产生从元素k~m的全排列，作为前k-1个元素的后缀
void perm(int list[],int k,int m)
{
int i,j;
if(k==m)//构成了一次全排列，输出结果
{
for(i=0;i<=m;i++)
cout<<list[i]<<‘ ’；
cout<<endl;
}
else//在数组list中，产生从元素k~m的全排列
{
for(j=k;i<=m;j++)
{
swap(list[k],list[j]);
perm(list,k+1,m);
swap(list[k],list[j]);
}
}
}
5.半数集问题
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下。
(1) n set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
例如，set(6)={6，16，26，126，36，136}。
半数集set(6)中有6个元素。
注意半数集是多重集。
对于给定的自然数n，编程计算半数集set(n)中的元素个数。
递归算法实现
int comp(int n)
{
int ans=1;
if(n>1)
for(int i=1;i<=n/2;i++)
ans+=comp(i);
return ans;
}
在此算法中，为了避免重复计算，可以使用记忆化搜索，改进效率
int a[1001];
int comp(int n)
{
int ans=1;
if(a[n]>0)return a[n]; //已经计算
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans; //保存结果
return ans;
}
作者：SDAU_Li
