递归和全排列

一、递归思想

1.明确你这个函数想要干什么

对于递归，要明确这个函数的功能，起到一个什么样的功能，要用来干什么。

//以求n的阶乘为例子
int jie(int n)//明确返回类型和参数，明确要用递归来求n阶乘
{
    return ;
}

2.寻找递归结束条件

递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，否则就会一直调用，而且调用的过深也会爆栈。我们需要找出当参数等于什么的时候，递归结束，之后直接把结果返回，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。例如，上面那个例子，当 n = 1 时，此时，f(1) = 1。

int jie(int n)
{
    if(n==1)//当n为1时递归到了最后一层，即递归的结束条件
        return 1;
    
    return ;
}

3.找出函数的等价关系式

我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。
例如，f(n) 这个范围比较大，我们可以让 f(n) = n * f(n-1)。这样，范围就由 n 变成了 n-1 了，范围变小了，并且为了原函数f(n) 不变，我们需要让 f(n-1) 乘以 n。
说白了，就是要找到原函数的一个等价关系式，f(n) 的等价关系式为 n * f(n-1)，即 f(n) = n * f(n-1)

int jie(int n)
{
    if(n==1)
        return 1;
    return n*jie(n-1);//n的阶乘=n*(n-1)的阶乘
}

注意：写递归的时候容易犯迷糊，总是感觉无从下手，当你写这一层的递归时，只需要考虑这一次的，后面递归的看成一个整体先不考虑，把这一层的写好。

二、全排列问题

1.用STL输出全排列 next_permutation(）函数

这个方法适用于需要输出全排列的场景，next_permutation()函数按照字典序排序，使用之前要先用sort（）给数据从小到大排序，得到最小排列，然后每调用一次next_permutation()函数，就可以得到大一点的排列

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int data[5]={3,5,4,2,1};
    sort(data,data+5);
    do{
        for(int i=0;i<5;i++)//变换完排列后将这次排列打印
            cout<<data[i]<<" ";
        cout<<endl;
    }while(next_permutation(data,data+5));//循环完一次变成稍大一点的排列
    return 0;
}

2.用递归求全排列（以求10个数的全排列为例子）

最简单暴力的方法就是写10个for循环嵌套，但是会非常复杂，如果用递归求会稍显简单一些

思路讲解

1.首先让第一个数不同，分成n个分支，每个分支后面排序、递归可以看成独立的不会重复和冲突。方法就是让当前10个数中的第一个数依次和后面的每个数交换一次位置。

以上n个数列由于第一个数不同，后面n-1个数无论怎样排列，得到的数列都是不同的。

2.去掉第一个数，对每个分支后面的n-1个数进行类似第一步的操作。

3.重复上述过程直到用完数字

#include<iostream>
using namespace std;
# define Swap(a,b){//直接用swap也行，但是会满一点
    int tem=a;
    a=b;
    b=tem;
}
int data[10]={1,2,3,4,5,6,7,8,9,10};
//具体数字只是举例子，根据具体情况也可以通过cin数字来进行
int sum=0;//记录一共有多少种排列
int perm(int begin,int end)//递归函数求全排列,参数为数组下标
{
    if(begin==end)//数字用完，代表已经完成这次排列
    {
        //这里可以加操作，如打印这次的排列
        sum++;//
    }
    else//这次排列未完成
    {
        for(int i=begin;i<=end;i++)
        {
            Swap(data[begin],data[i]);//将当前数列的第一个数字依次和后面的数字交换
            perm(begin+1,end);//第一个数字每换一个就为一个新的分支
            Swap(data[begin],data[i]);//恢复，用于下一次交换
        }
    }
}
int main()
{
    cout<<sum<<endl;
    return 0;
}

如果要打印n个数中任意m个数的组合，只需要把结束条件改为begin==m就行