算法设计与分析——递归

递归是一种技术手段，并不严格算是一种算法，是指程序直接间接调用自身的编程技巧。

递归需要有边界条件，递归前进段和递归返回段。
（1）当边界条件不满足时，递归前进；
（2）当边界条件满足时，递归返回。
PS：在使用递归策略时，必须有一个明确的递归结束条件，成为递归出口，否则将无限进行下去

递归的缺点：
*递归算法解体的运行效率低。
在递归调用过程中，系统为每一层的返回点、局部变量等开辟了堆栈来存储。递归次数多容易造成堆栈溢出等

例题一：
Fibonacci数列：
int fib（int n）
{
if(n<=1)
return 1;
return fib(n-1)+fib(n-2);
}

例题二：
集合的全排列问题

void perm(int list[],int k,int m)
{
if(k==m)
{
for(int i=0;i<=m;++i)
cout<<list[i]<<" ";
cout<<endl;
}
else
{
for(int j=k;j<=m;++j)
{
swap(list[k],list[j]);
perm(int list[],int k+1,int m);
swap(list[k],list[j]);
}
}
}

例题三：
整数划分

int spilt(int n,int m)
{
if(n1||m1)
return 1;
else if(n<m)
return spilt(n,n);
else if(n==m)
return spilt(n,n-1)+1;
else
return spilt(n,m-1)+spilt(n-m,m);
}